Сжатие и поиск огромного списка слов

Question

У меня есть огромный список многобайтовых последовательностей (давайте назовем их словами), которые мне нужно сохранить в файле и которые я должен иметь возможность быстрого поиска. Огромные означает: около 2 миллионов из них, каждый длиной 10-20 байт.

Кроме того, каждое слово должно иметь значение tag , связанное с ним, чтобы я мог использовать его для ссылки на дополнительные (внешние) данные для каждого элемента (следовательно, словарь проверки орфографии здесь не работает так, как только обеспечивает хит-тест).

Если бы это было только в памяти, и если бы памяти было много, я мог бы просто сохранить все слова в хешированной карте (словарь, пары ключ-значение) или в отсортированном списке для двоичного поиска.

Однако я бы хотел сильно сжать данные, а также предпочел бы не считывать данные в память, а искать в файле.

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

Может кто-нибудь указать мне эффективную технику или алгоритм для этого?

Или даже примеры кода?

Обновление

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

На самом деле, это, вероятно, путь:

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

Теперь, если это жизнеспособно, как я на самом деле найду часто используемые подпоследовательности во всех моих фразах? Приблизительно с 2 миллионами фраз, состоящих обычно из 1-3 слов, будет трудно выполнить все перестановки всех возможных подстрок ...

Answer 1

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

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

Эта структура дает: а) Быстрый поиск. После слова длины n вы можете найти строку в n ссылок в дереве. б) Сжатие. Общие префиксы сохраняются.

Пример: слова BANANA и BANAL будут иметь равные узлы B, A, N, A, и тогда последний (A) узел будет иметь 2 дочерних элемента, L и N. Ваши узлы также могут хранить другую информацию о слове.

(http://en.wikipedia.org/wiki/Trie)

Andrew JS

Answer 2

Я бы рекомендовал использовать Trie или DAWG (ориентированный ациклический граф слов).Здесь есть отличная лекция из Стэнфорда о том, как делать именно то, что вы хотите: http://academicearth.org/lectures/lexicon-case-study

Answer 3

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

Answer 4

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

И, как указывает jkff, ваш список будет составлять всего около 40 МБ, что не так уж много.

Answer 5

Вам следует ознакомиться с индексированным файлом.