Datenstruktur für eine große Anzahl von Mustern

Question

In einem Interview wurde ich gebeten, eine Datenstruktur zu entwickeln, die Millionen von Mustern enthalten kann und eine schnelle Suche durch sie ermöglicht, um die am längsten übereinstimmende zu finden.

Zum Beispiel Muster sind wie:

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

die Eingabe eine Zahl mit mindestens 2 und höchstens 18 Stellen, und wir brauchen die längsten Übereinstimmungsmuster aus der Datenstruktur zu finden und zu extrahieren, die Boolesche an das Ende.

Zum Beispiel würde 8876 8893 9943 53 die 1 entsprechen und true zurückgegeben wird. 8876 8397 5430 74 würde die 3 entsprechen und false zurückgegeben wird.

Meine Antwort war, einen Baum zu verwenden und eine Liste von key value Paar auf jeder Ebene zu haben. Der Schlüssel ist die Zahl und der Wert ist entweder null oder gleich boolesch, abhängig davon, ob es das Ende eines Musters ist oder nicht. Wie:

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

Der schwierige Teil ist, dass die Muster ziemlich viel sind. Millionen von ihnen. Ist das gut? Wenn nicht, was ist dein Vorschlag?

Answer 1

Eine sehr nette Datenstruktur, die sehr gut zu dem von Ihnen beschriebenen Problem passt, dh eine Sammlungsstruktur, in der viele der Einträge ein gemeinsames Präfix (und/oder Suffix) haben und auf der Suche nach einem gemeinsamen Präfix durchgeführt wird a Trie.

In computer science ein trie auch digitaler Baum genannt und manchmal radix tree oder Präfixbaum (wie sie von Präfixen durchsucht werden können), ist eine geordnete Baumdatenstruktur, die verwendet wird, eine zum Speichern von dynamisches Set oder assoziatives Array, wobei die Schlüssel normalerweise Strings sind. Im Gegensatz zu einem binären Suchbaum speichert kein Knoten in dem Baum den Schlüssel, der diesem Knoten zugeordnet ist; Stattdessen definiert seine Position im Baum den Schlüssel, mit dem es verknüpft ist. Alle Nachkommen eines Knotens haben eine gemeinsame prefix der Zeichenfolge, die diesem Knoten zugeordnet ist, und der Stamm ist der leeren Zeichenfolge zugeordnet. Werte sind normalerweise nicht jedem Knoten zugeordnet, sondern nur mit Blättern und einigen inneren Knoten, die Schlüsseln von Interesse entsprechen. Informationen zur platzoptimierten Darstellung des Präfixbaums finden Sie unter compact prefix tree.

Insbesondere die kompakten Präfixbaums oder patricia trie scheint für Ihr Problem gut geeignet zu sein.

Vorausgesetzt, dass die genannten Arten von Versuchen häufig verwendet werden, um mit Schlüsseln verknüpfte Werte zu speichern, wenn dies für Ihr Problem nicht erforderlich ist (dh Sie müssen den ursprünglichen Index der Eingabemusterzeichenfolge nicht speichern und auf a zurückgeben Suche) gibt es eine eng verwandte Lösung, die vielleicht noch besser passt. Wie von @JimMischel in den Kommentaren bemerkt, baut die Aho–Corasick string matching algorithm eine Trie-ähnliche Struktur mit zusätzlichen Verbindungen zwischen den internen Knoten. Wenn die Menge der übereinstimmenden Muster festgelegt ist und die Datenstruktur aufgebaut ist, ist ihre Laufzeit für eine Suche linear in der Länge der Eingabe plus der Anzahl übereinstimmender Einträge.

Es ist so in dieser diskutiert Aho Corasick algorithm

Sie fragen einige Implementierungen es online in zum Beispiel C# oder Java oder Haskell finden.

Answer 2

Sie könnten die Implementierung von wu-manber in Betracht ziehen, die einfach zu programmieren und speichereffizient ist.