DawgSharp
1.0.0
[NuGet-Paket] [Kommerzielle Lizenz erhalten]
DAWG (Directed Asymmetric Word Graph) ist eine Datenstruktur zum Speichern und Durchsuchen großer Wortlisten und Wörterbücher. Für bestimmte Datentypen kann sie 40-mal effizienter sein als die .NET Dictionary Klasse.
Beispielsweise hostet meine Website ein Wörterbuch mit 2 Millionen Wörtern, das früher 56 MB auf der Festplatte belegte und dessen Ladezeit 7 Sekunden dauerte (bei Verwendung von Dictionary und BinarySerializer). Nach dem Wechsel zu DAWG benötigt es jetzt 1,4 MB auf der Festplatte und 0,3 Sekunden zum Laden.
Wie ist das möglich? Warum ist das Standardwörterbuch nicht so clever wie DAWG? Die Sache ist die, dass DAWG gut mit Zeichenfolgen in natürlicher Sprache funktioniert und möglicherweise nicht so gut für generierte Zeichenfolgen wie Lizenzschlüssel (OIN1r4Be2su+UXSeOj0TaQ). Wörter in menschlicher Sprache haben in der Regel viele gemeinsame Buchstabenfolgen, z. B. -ility in Fähigkeit , Möglichkeit , Beweglichkeit usw., und der Algorithmus macht sich dies zunutze, indem er diese Folgen findet und sie für mehrere Wörter nur einmal speichert. DAWG hat sich auch bei der Darstellung von DNA-Daten (Gensequenzen) als nützlich erwiesen. Die Geschichte von DAWG reicht bis ins Jahr 1985 zurück. Für weitere Hintergrundinformationen googeln Sie DAWG oder DAFSA (Deterministic Asymmetric Finite State Automaton).
DawgSharp ist eine Implementierung von DAWG, eine von vielen. Was macht es besonders?
Load/Save auf, um die Daten auf die Festplatte zu schreiben und zurückzulesen.In diesem Beispiel simulieren wir ein Nutzungsszenario mit zwei Programmen, eines zum Generieren des Wörterbuchs und Schreiben auf die Festplatte und das andere zum Laden dieser Datei und zum Verwenden des schreibgeschützten Wörterbuchs für Suchvorgänge.
Rufen Sie zunächst den Code ab, indem Sie dieses Repository klonen oder das NuGet-Paket installieren.
Erstellen und füllen Sie ein DawgBuilder -Objekt:
var words = new [ ] { " Aaron " , " abacus " , " abashed " } ;
var dawgBuilder = new DawgBuilder < bool > ( ) ; // <bool> is the value type.
// Key type is always string.
foreach ( string key in words )
{
dawgBuilder . Insert ( key , true ) ;
} (Alternativ führen Sie var dawgBuilder = words.ToDawgBuilder(key => key, _ => true); aus.)
Rufen Sie BuildDawg auf, um die komprimierte Version abzurufen und auf der Festplatte zu speichern:
Dawg < bool > dawg = dawgBuilder . BuildDawg ( ) ;
// Computer is working. Please wait ...
using ( var file = File . Create ( " DAWG.bin " ) )
dawg . SaveTo ( file ) ;Lesen Sie nun die Datei erneut ein und prüfen Sie, ob ein bestimmtes Wort im Wörterbuch enthalten ist:
var dawg = Dawg < bool > . Load ( File . Open ( " DAWG.bin " ) ) ;
if ( dawg [ " chihuahua " ] )
{
Console . WriteLine ( " Word is found. " ) ;
} Die Klassen Dawg und DawgBuilder verwenden einen Vorlagenparameter namens <TPayload> . Es kann jeder gewünschte Typ sein. Um zu testen, ob ein Wort im Wörterbuch vorhanden ist, reicht ein Bool aus. Sie können es auch zu einem int , einem string oder einer benutzerdefinierten Klasse machen. Beachten Sie jedoch eine wichtige Einschränkung. DAWG funktioniert nur dann gut, wenn die Menge der Werte, die TPayload annehmen kann, relativ klein ist. Je kleiner desto besser. Wenn Sie beispielsweise für jedes Wort eine Definition hinzufügen, wird jeder Eintrag einzigartig und Ihr Diagramm wird zu einem Baum (was vielleicht nicht so schlimm ist!).
Ein weiterer attraktiver Aspekt von DAWG ist seine Fähigkeit, effizient alle Wörter abzurufen, die mit einer bestimmten Teilzeichenfolge beginnen:
dawg . MatchPrefix ( " awe " ) Die obige Abfrage gibt ein IEnumerable<KeyValuePair> zurück, das Schlüssel wie awe, aweful und awesome enthalten kann. Der Aufruf dawg.MatchPrefix("") gibt alle Elemente im Wörterbuch zurück.
Wenn Sie stattdessen nach Suffixen suchen müssen, gibt es keine MatchSuffix-Methode. Der gewünschte Effekt kann jedoch erzielt werden, indem man die umgekehrten Schlüssel hinzufügt und dann MatchPrefix() auf die umgekehrten Schlüssel anwendet:
dawgBuilder . Insert ( " ability " . Reverse ( ) , true ) ;
.. .
dawg . MatchPrefix ( " ility " . Reverse ( ) ) GetPrefixes() gibt alle Wörterbuchelemente zurück, deren Schlüssel Teilzeichenfolgen einer bestimmten Zeichenfolge sind. Zum Beispiel:
dawg . GetPrefixes ( " awesomenesses " )Könnte Schlüssel wie awe, awesome, awesomeness und schließlich awesomenesses zurückgeben.
Eine weitere nette Funktion ist die Methode int GetLongestCommonPrefixLength(IEnumerable<char> word) . Wenn word im Wörterbuch gefunden wird, wird dessen Länge zurückgegeben. Wenn nicht, wird die Länge des längsten im Wörterbuch gefundenen Wortes zurückgegeben, das auch der Anfang des angegebenen Wortes ist. Wenn sich beispielsweise „preempt“ im Wörterbuch befindet, preempt jedoch nicht, dann gibt dawg.GetLongestCommonPrefixLength("preempt") 3 zurück, was der Länge von „pre“ entspricht.
Die DawgBuilder -Klasse ist nicht threadsicher und darf zu einem bestimmten Zeitpunkt nur von einem Thread aufgerufen werden.
Die Dawg -Klasse ist unveränderlich und somit threadsicher.
Die MultiDawg-Klasse kann auf sehr speichereffiziente Weise mehrere Werte gegen einen einzelnen Zeichenfolgenschlüssel speichern.
Die API wurde für ein bestimmtes Nutzungsszenario entwickelt (siehe oben) und kann erweitert werden, um andere Szenarien zu unterstützen, z. B. um neue Wörter zum Wörterbuch hinzuzufügen, nachdem es komprimiert wurde. Ich brauchte das einfach nicht, daher ist es nicht implementiert. Sie erhalten keine Ausnahmen. Es gibt einfach keine Insert -Methode für die Dawg -Klasse.
Implementieren Sie die IDictionary-Schnittstelle sowohl auf DawgBuilder als auch auf Dawg (#5).
DawgSharp ist unter GPLv3 lizenziert, was bedeutet, dass es kostenlos in Open-Source-Projekten verwendet werden kann. Lesen Sie die vollständige Lizenz
Wenn Sie DawgSharp in einem proprietären Projekt verwenden möchten, erwerben Sie bitte eine kommerzielle Lizenz unter http://morpher.co.uk.
