Struktura danych dla dużej liczby wzorów

Question

W jednym z wywiadów poproszono mnie o stworzenie struktury danych, która może pomieścić miliony wzorów i umożliwia szybkie wyszukiwanie, aby znaleźć najdłuższy pasujący.

Na przykład, wzory są jak:

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

Wejście jest liczbą z co najmniej 2 i co najwyżej 18 cyfr i musimy znaleźć najdłuższe dopasowanie wzorca ze struktury danych i wyodrębnić wartość logiczną na koniec.

Na przykład 8876 8893 9943 53 będzie pasować do 1 i zostanie zwrócona true. 8876 8397 5430 74 zostanie dopasowany do 3 i zostanie zwrócona false.

Moja odpowiedź polegała na używaniu drzewa i posiadaniu listy key value pary na każdym poziomie. Klucz będący cyframi i wartościami ma wartość null lub jest równa wartości logicznej, w zależności od tego, czy jest to koniec wzorca, czy nie. Podobnie jak:

# 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) 

Najtrudniejszą częścią jest to, że wzory są całkiem spore. Miliony z nich. Czy to jest dobre? Jeśli nie, jaka jest Twoja sugestia.

Answer 1

Bardzo dobra struktura danych, która bardzo dobrze pasuje do opisywanego problemu, tj. Struktura kolekcji, w której wiele wpisów ma wspólny przedrostek (i/lub sufiks), i gdzie przeprowadzane są wyszukiwania oparte na wspólnym przedrostku, a Trie.

W computer science, A trie, zwany także cyfrowy drzewo a czasem radix tree lub prefiks drzewo (ponieważ mogą one być przeszukiwane przez przedrostków), jest uporządkowana struktura danych drzewo, które służy do przechowywania zestaw dynamiczny lub tablica asocjacyjna, w której klucze są zwykle ciągami. W przeciwieństwie do binarnego drzewa wyszukiwania żaden węzeł w drzewie nie przechowuje klucza skojarzonego z tym węzłem; zamiast tego jego pozycja w drzewie definiuje klucz, z którym jest skojarzony. Wszyscy potomkowie węzła mają wspólny prefix ciąg skojarzony z tym węzłem, a korzeń jest powiązany z pustym łańcuchem. Wartości zwykle nie są powiązane z każdym węzłem, tylko z liśćmi i niektórymi wewnętrznymi węzłami, które odpowiadają kluczowym kluczom. Aby uzyskać zoptymalizowaną przestrzennie prezentację drzewa prefiksów, zobacz compact prefix tree.

Konkretnie kompaktowy drzewo przedrostek lub Patricia trie wydaje się być dobrze nadaje się do problemu.

Biorąc pod uwagę, że wspomniane typy prób są często używane do przechowywania wartości skojarzonych z kluczami, jeśli nie jest to wymagane dla twojego problemu (tzn. Nie musisz przechowywać oryginalnego indeksu ciągów wzorców wejściowych i zwracać je na wyszukiwanie), istnieje ściśle powiązane rozwiązanie, które może pasować jeszcze lepiej. Jak zauważyli @JimMischel w komentarzach, Aho–Corasick string matching algorithm buduje strukturę typu Trie z dodatkowymi łączami między węzłami wewnętrznymi. Jeśli zestaw wzorców, które mają zostać dopasowane, jest stały, a struktura danych jest zbudowana, wówczas dla przeszukiwania jego czas działania jest liniowy na długości wejścia plus liczba dopasowanych wpisów.

Jest to omówione w SO pytanie Aho Corasick algorithm

Można znaleźć kilka implementacje online w nim na przykład C# lub Java lub Haskell.

Answer 2

Można rozważyć implementację wu-manber, która jest łatwa do kodowania i wydajnej pamięci.