Ответ 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, вероятно, будет слишком дорогостоящим для хранения очень большого набора данных. Но в случае, если нет готового решения, это то, что я попытаюсь сделать первым...