Как более эффективно хранить словарный запас в массиве?

У меня есть словарный запас, a, abandon, ..., z.

По какой-то причине я буду использовать для их хранения массив, а не Trie.

Таким образом, простой метод может быть: wordA\0wordB\0wordC\0...word\0

Но я думаю, что есть еще несколько экономичных методов для памяти.

Поскольку like является подстрокой likely, мы можем сохранить только первую позицию и длину like вместо самой строки. Таким образом, мы генерируем «большую строку», содержащую все слова словаря, и используем position[i] и length[i] для получения i-го слова.

Например, словарный запас содержит три слова ab, cd и bc. Я создаю abcd как "большую строку".

position[0] = 0, length[0] = 2

position[1] = 2, length[1] = 2

position[2] = 1, length[2] = 2

Итак, как сгенерировать «большую строку» — это ключ к этой проблеме, есть ли какие-нибудь интересные предложения?

Я думаю, что проблема похожа на проблему TSP (задача коммивояжера), которая является проблемой NP.


arrays algorithm vocabulary
person LTzycLT    schedule 16.11.2015    source источник
comment
Есть ли причина не использовать существующее решение для базы данных? Конечно, вы можете придумать свой собственный. Но стоит ли это усилий?   -  person clq    schedule 16.11.2015
comment
@clq: я не думаю, что реляционные БД сжимают таблицы строк до Trie или чего-то еще. Поправьте меня, если я ошибаюсь, но таблица БД с одним строковым полем в качестве первичного ключа даст вам очень быструю проверку индекса на наличие/отсутствие, но, вероятно, займет больше места, чем хранение их всех в обратном порядке. назад в струне C.   -  person Peter Cordes    schedule 16.11.2015
comment
@clq Array более эффективен и прост в обращении для проекта на чистом C.   -  person LTzycLT    schedule 16.11.2015
comment
@LTzycLT: более эффективное использование пространства, но менее эффективное по времени, чем при использовании готовой базы данных. Библиотека БД даст вам хорошую производительность, не тратя на нее много времени на разработку.   -  person Peter Cordes    schedule 16.11.2015
comment
что не так с трио? Структура, о которой вы говорите, кажется мне очень ограничительной... или, скажем иначе: она может принести пользу только в очень специфических случаях. Вы приводите пример, где слово является префиксом другого - нравится и вероятно.. Но что, если они только разделяют префикс. За мгновенные лайки и лайки. Как ваш массив должен эффективно хранить эти два слова? Ну, попробовать было бы идеально для этого, я думаю...   -  person dingalapadum    schedule 16.11.2015
comment
Поиск оптимального решения вполне может быть полным NP, как вы догадываетесь. Оптимальный был бы хорош, но вы всегда можете согласиться на достаточно хороший, как это делает gzip / lzma / lzop / lz4 / bzip / любой другой компрессор. Я согласен с @dingalapadum: эта схема сжатия не имеет большого преимущества. Я предполагаю, что это позволяет вам выполнять бинарный поиск без распаковки всего словаря, но мой ответ предлагает некоторые структуры данных лучше, чем Trie, которые также эффективны для поиска.   -  person Peter Cordes    schedule 16.11.2015
comment
@PeterCordes спасибо за совет   -  person LTzycLT    schedule 16.11.2015
comment
@PeterCordes Я даже не думаю, что это позволяет вам выполнять бинарный поиск. Двоичный поиск предполагает некоторую упорядоченность. Но я не думаю, что вы можете гарантировать такой порядок здесь. Рассмотрим: {да, день, вчера} => длинное слово вчера + маркеры (0,2), (0,8), (6, 8). Итак, как мы можем эффективно проверить, стоит ли день в dict? Или я что-то упускаю? Кроме непрерывности в памяти, я не вижу в этой структуре ничего полезного. И что хорошего в том, чтобы быть смежным, если все остальное отстой? Интересными операциями обычно являются: вставить, удалить и найти, для всех этих операций эта штука кажется мне отстойной.   -  person dingalapadum    schedule 16.11.2015
comment
@dingalapadum Мой словарный запас уже в алфавитном порядке.   -  person LTzycLT    schedule 16.11.2015
comment
@dingalapadum: вы не можете искать в своем примере, потому что ваш словарь не отсортирован. Поскольку вы можете получить i слово за постоянное время (произвольный доступ к словам), вы можете выполнять двоичный поиск, если записи в pos / length упорядочены. Нет никакого преимущества в том, что массивы pos/length не в порядке, потому что каждый pos занимает, вероятно, 16-битное uint16_t, а каждая запись length занимает 8-битное uint8_t.   -  person Peter Cordes    schedule 16.11.2015
comment
@dingalapadum: я думаю, что вы упускаете то, что длинная строка не обязательно должна содержать слова по порядку. т.е. pos[] записи не обязательно должны монотонно возрастать.   -  person Peter Cordes    schedule 16.11.2015
comment
@PeterCordes ах, как плохо .. Теперь я понимаю, что вы имеете в виду. Вы сортируете записи pos/length по слову, которое они представляют.   -  person dingalapadum    schedule 16.11.2015
comment
@PeterCordes Хорошо. Но если я понимаю это прямо сейчас, то вы выполняете бинарный поиск по словам, когда ваша первая буква совпадает со словом, которое вы нашли, вы запускаете поиск, линейный по размеру слова... и если вы не соответствуете, вы Полагаю, я продолжу бинарный поиск... так что на самом деле он работает за O(log (number_of_words)*size_of_longest_word), верно?   -  person dingalapadum    schedule 16.11.2015
comment
@LTzycLT Мне все еще интересно, чего вы ожидаете от общих префиксов ... лайк, лайк, лайкер, лайк? Как бы вы сохранили эти 4 слова?   -  person dingalapadum    schedule 16.11.2015
comment
@dingalapadum: да, если N = количество слов в словаре, а M = длина слова, которое вы ищете, в худшем случае будет O (M log N), а в среднем, вероятно, просто O (log N) , потому что memcmp(needle, bigstr[pos[i]], len[i]) обычно быстро находит разницу. Что касается общих префиксов: ОП никогда не утверждал, что это помогло с общими префиксами. Возможно, в его словаре много слов, являющихся подстроками других слов, а не много разных форм одного и того же слова. Или, может быть, он просто хочет попробовать эту идею, хотя для английского она, вероятно, не сработает.   -  person Peter Cordes    schedule 16.11.2015
comment
@dingalapadum В этом случае я не могу объединить буквы из этих четырех слов. Так что, возможно, это не лучший способ сделать компресс. Но массив, который является необходимой структурой данных, определен, я хотел бы подумать о другом способе сжатия слов в массиве. В любом случае, спасибо за ваш ответ.   -  person LTzycLT    schedule 16.11.2015

Ответы (1)


arrow_upward
0
arrow_downward

Ключевое слово, которое вы ищете, — «словарь». т. е. структуры данных, которые можно использовать для хранения списка слов и проверки наличия или отсутствия других строк в словаре.

Ваша идея более компактна, чем хранение каждого слова отдельно, но намного менее компактна, чем хорошая структура данных, такая как DAWG. Как вы заметили, не очевидно, как оптимально выбрать способ перекрытия ваших строк. То, что вы делаете, немного похоже на схему сжатия без потерь (например, gzip). Если вам не нужно сверять слова с компактным словарем, можно просто использовать gzip или LZMA для сжатия отсортированного списка слов. Пусть их алгоритмы найдут избыточность и представят ее компактно.

Я просмотрел словари для недавнего ответа SO, который меня заинтересовал: #32537772">Внешняя сортировка строк с ограничением памяти, с объединением и подсчетом дубликатов на критическом сервере (миллиарды имен файлов)

Для словаря, в который не нужно добавлять новые слова на лету, можно использовать направленный ациклический граф слов это путь. Вы сопоставляете строку с ней, следуя узлам графа, пока либо не достигнете точки, где нет ребра, соответствующего следующему символу, либо вы не дойдете до конца вашей входной строки и не обнаружите, что узел в DAWG помечен как допустимый конец -от слова. (Вместо того, чтобы просто подстрока, которая является только префиксом некоторых слов). Существуют алгоритмы для построения этих автоматов из простого словаря массива слов за разумное время.

Ваш метод может использовать избыточность только тогда, когда целое слово является подстрокой другого слова или концом одного или началом другого. DAWG может использовать общие подстроки повсюду, а также довольно быстро сопоставлять слова. Вероятно, сравнимая скорость с двоичным поиском вашей структуры данных, особенно. если гигантская строка слишком велика, чтобы поместиться в кэш. (Как только вы начинаете превышать размер кэша, компактность структуры данных начинает перевешивать сложность кода для скорости.)

Менее сложным, но все же эффективным является Trie (или Radix Trie), где общие префиксы объединяются, но общие подстроки позже в словах снова не сходятся.

Если вам вообще не нужно изменять DAWG или Trie, вы можете эффективно хранить их в одном блоке памяти, а не динамически выделять каждый узел. Вы не сказали, почему не хотите использовать Trie, а также не признали существование других структур данных, которые выполняют эту работу лучше, чем простой Trie.

person Peter Cordes    schedule 16.11.2015
comment
Вы читали вопрос ОП? конкретно: For some reason, I will use array rather than Trie. Он дал понять, каким методом хочет воспользоваться, а вы не отвечаете на вопрос: how to generate the "large string" - person fjardon; 16.11.2015
comment
@fjardon: Ой, нет, я пропустил это, когда просматривал. Я просто обновлял свой ответ, чтобы немного лучше ответить на вопрос или, по крайней мере, указать, что то, что он хочет, похоже на то, что делают схемы сжатия без потерь, такие как gzip (и предлагаю использовать это). Может быть, посмотрите на них для вдохновения. Вы правы в том, что этот ответ не дает прямого ответа на вопрос, заданный ОП, а вместо этого пытается предложить что-то, что решит ту же проблему по-другому. - person Peter Cordes; 16.11.2015