Эффективно хранимый словарь. Существует ли эта структура данных и что она называется?

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

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

dict:
1: 'The quick brown fox jumps over the lazy dog.'
2: 'The quick green frog jumps over the lazy fox.'
3: 'The quick brown fox jumps over the lazy frog.'

Если два предложения одинаковы, они должны иметь один и тот же индекс.

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

dict.get(1) => 'The quick brown fox jumps over the lazy dog.'
dict.match('The quick brown *') => [1, 3]

Я мог бы сжать каждое предложение, но это пренебрегает тем фактом, что многие записи похожи.

Я мог бы сортировать их и хранить diff. но это очень сложно добавить и удалить элементы.

Он должен поддерживать unicode.

Я уверен, что есть какая-то древовидная структура, которая делает это.

Бонусные баллы, если у них есть оболочка python.

Этот https://hkn.eecs.berkeley.edu/~dyoo/python/suffix_trees/ выглядит очень близко, но не видел действия с 2002 года /py 2.2, и я не мог заставить его работать. Если есть новые или лучшие альтернативы для проверки, я хотел бы услышать о них.

Я включаю тег биоинформатики, потому что понимаю, что там используются суффиксы и аналогичные структуры данных.

Ответ 1

Как вы уже указали, суффиксом или деревом оснований, вероятно, является путь. Я бы предложил:

Создание дерева оснований, сохраняющее идентификаторы в листах. Проверьте ссылки в этом ответе для начала, но я считаю, что вам нужно будет точно настроить все, что вы найдете в соответствии с вашими потребностями;
Создание идентификаторов отображения dict для путей в дереве. Это позволит вам быстро получить предложения по id (найдите путь, следуйте за ним, чтобы установить предложение). Обратите внимание, что это сделает вставки и удаляет бит дорого: каждый раз, когда изменяется не-лист node, каждый потомок должен обновлять свои пути в dict;

2,1. Альтернатива (в случае, если пути заканчиваются слишком долго) состоит в том, чтобы каждый node хранил ссылку на своего родителя, поэтому dict нужно только ссылаться на лист node. Я считаю, что большинство реализаций там не делают, поскольку основная цель попыток - ускорить поиск, а не сжимать сам текст.
Поиск подстановочных знаков немного сложнее, в зависимости от сложности ваших потребностей. Приведенный пример прост: следуйте за узлами для префикса, пока не будет найден шаблон, затем верните все потомки. В этом случае общее правило trie может быть проще, чем более специализированное дерево оснований, но требования в пространстве немного выше.

Кстати, вы могли бы также оптимизировать ваше radix trie, чтобы сделать меньше места, ~~, используя некоторую косвенность~~, интернируя строки в узлах и добавляя дополнительные узлы для длинных общих подстрок. Пример:

unique_strings = [ # Not a real array, just an hypothetical "intern table"
    "The quick ",
    "brown fox ",
    "green frog ",
    "jumps over the lazy ",
    "dog.",
    "fox.",
    "frog.",
]
radix_trie = (0, {        # The quick *
    "b":(1, {             # The quick brown fox *
        "j":(3, {         # The quick brown fox jumps over the lazy *
            "d":(4,{},1), # The quick brown fox jumps over the lazy dog.
            "f":(6,{},3), # The quick brown fox jumps over the lazy frog.
        }),
    }),
    "g":(2, {             # The quick green frog *
        "j":(3, {         # The quick green frog jumps over the lazy *
            "f":(5,{},2), # The quick green frog jumps over the lazy fox.
        }),
    }),
})
# The nodes ("b", "j") and ("g", "j") wouldn't occur in a regular radix tree,
# since they have no siblings. Adding them, however, gives a net gain of space.
#
# "jumps over the lazy " is a common substring of
#     "brown fox jumps over the lazy " and
#     "green frog jumps over the lazy fox."
# which would occur naturally in a radix tree with only the 3 sentences given.
paths = {
    1:("b", "j", "d"),
    2:("g", "j", "f"),
    3:("b", "j", "f"),
}

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

Примечание. Я предлагаю дерево radix вместо trie, потому что требования к пространству для первых намного меньше.

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

Используя ваш пример, базовое дерево "регулярных" (без одиноких детей) будет:

radix_tree = ("The quick ", {
    "b":("brown fox jumps over the lazy ", {
        "d":("dog.",{},1),
        "f":("frog.",{},3),
    }),
    "g":("green frog jumps over the lazy fox.", {}, 2),
})

который явно не делает большой работы по сжатию вашего текста. Но после создания дерева суффиксов для набора слов в каждом node становится ясно, что " jumps over the lazy " является хорошим кандидатом для интернирования и повторного использования в двух или более узлах (в результате показан пример, который я показал ранее). Сохраненное пространство всегда будет (string_length - (1..2)*sizeof_node) * num_nodes (1 для префикса/суффикса, 2 для отдыха), поэтому при выполнении этой оптимизации короткие строки вообще не нужно рассматривать.

Комплекс, да, и, как отметил Адам Михалцин, чистое решение Python, вероятно, будет слишком дорогостоящим для хранения очень большого набора данных. Но в случае, если нет готового решения, это то, что я попытаюсь сделать первым...

Ответ 2

Ваша проблема звучит точно так же, как в случае использования trie, которая представляет собой древовидную структуру данных для хранения строк с помощью префикса. Я сам не использовал эти реализации, но быстрый поиск в коде Google показывает проекты trie с открытым исходным кодом здесь и здесь и здесь. Первые два находятся на Java, а третий - на С++. Я бы ожидал, что писать обертку вокруг С++ для Python было бы проще, чем писать обертку вокруг Java, поскольку Python имеет встроенные возможности для взаимодействия с C.

ИЗМЕНИТЬ

Я проверил GitHub и имел немного больше успеха с реализациями Python. Я нашел Python trie реализаций здесь и здесь и здесь.

Однако, если вы действительно работаете с миллиардом предложений, даже очень хорошо написанная чистая реализация Python (как и все три из них) может закончиться без памяти.