Структура данных для большого числа шаблонов

Question

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

Например, узоры, как:

1- 8876 8893 87   | true 
2- 8876 889    | false 
3- 8876 8    | false 
4- 887     | true 

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

Например, 8876 8893 9943 53 будет соответствовать 1 и true. 8876 8397 5430 74 будет соответствовать 3 и false.

Ответом было использование дерева и наличие пары key value на каждом уровне. Ключ, являющийся цифрами и значением, является либо нулевым, либо равным логическому в зависимости от того, является ли это концом шаблона или нет. Нравится:

# matching 8875 
# start the search by first digit 
[..., (7, null), (8, null), (9, null)] 
       ^
       [..., (7, null), (8, null), (9, null)] 
           ^
            [..., (7, true), (8, null), ...] 
# at the last step because we don't have a pattern 
# to match the digit 5, we return the `true` from (7, true) 

Сложная часть заключается в том, что узоры довольно много. Миллионы из них. Это хорошо? Если нет, то каково ваше предложение.

Answer 1

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

В computer science, А Trie, называемое также цифрового деревом, а иногда radix tree или префикс дерево (так как они могут быть найдены по префиксам), представляет собой упорядоченную структуру данных дерева, которая используется для хранения динамический набор или ассоциативный массив, где ключи обычно являются строками. В отличие от дерева двоичного поиска ни один узел в дереве не сохраняет ключ, связанный с этим узлом; вместо этого его позиция в дереве определяет ключ, с которым он связан. Все потомки узла имеют общую строку prefix строки, связанной с этим узлом, а корень связан с пустой строкой. Значения обычно не связаны с каждым узлом, только с листьями и некоторыми внутренними узлами, которые соответствуют интересующим ключам. Для пространственно-оптимизированного представления дерева префикса см. compact prefix tree.

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

Учитывая, что указанные типы попыток часто используются для хранения значений, связанных с ключами, если это не требуется для вашей проблемы (т. Е. Вам не требуется хранить исходный индекс строки шаблонов ввода и возвращать это значение на поиск), существует тесно связанное решение, которое может поместиться еще лучше. Как отметил @JimMischel в комментариях, Aho–Corasick string matching algorithm строит подобную trie структуру с дополнительными связями между внутренними узлами. Если набор шаблонов, подлежащих сопоставлению, является фиксированным, а структура данных построена, то для поиска его время выполнения является линейным по длине ввода плюс количество согласованных записей.

Это обсуждается в этом SO вопрос Aho Corasick algorithm

Вы можете найти некоторые реализации его в Интернете, например, в C# или Java или Haskell.

Answer 2

Вы можете рассмотреть возможность внедрения wu-manber, который также прост в использовании кода и памяти.