Guten Algorithmus und Datenstruktur für das suchen nach Wörtern mit fehlenden Buchstaben?

Angesichts der aktuellen Einschränkungen:

• Es werden bis zu 2 Fragezeichen
• Es gibt 2 Fragezeichen, erscheinen Sie zusammen
• Gibt es ~100.000 Wörter im Wörterbuch, die Durchschnittliche Wortlänge 6.

Habe ich zwei praktikable Lösungen für Sie:

Die schnelle Lösung: HASH

Können Sie ein hash-welche Tasten sind Ihre Wörter mit bis zu zwei '?', und die Werte werden in einer Liste passende Worte. Dieser hash wird mit rund 100,000 + 100,000*6 + 100,000*5 = 1,200,000 Einträge (wenn Sie 2 Fragezeichen, Sie brauchen nur den Ort zu finden, der erste...). Jeder Eintrag speichert eine Liste von Wörtern, oder eine Liste von Zeigern auf die vorhandenen Wörter. Wenn Sie speichern eine Liste von Zeigern, und wir gehen davon aus, dass es im Durchschnitt weniger als 20 Wörter matching jedes Wort mit zwei '?', dann wird der zusätzliche Speicher ist kleiner als 20 * 1.200.000 werden = 24.000.000 ist.

Wenn jeder Zeigergröße 4 bytes, dann der Speicherbedarf ist hier (24.000.000 ist+1.200.000 werden)*4 bytes = 100,800,000 Byte ~= 96 mega-Byte.

Fazit dieser Lösung:

• Speicherverbrauch: ~96 MB
• Zeit für jede Suche: berechnen einer hash-Funktion, und nach einem Zeiger. O(1)

Hinweis: wenn Sie möchten, verwenden Sie einen hash, der eine kleinere Größe, die Sie können, aber dann ist es besser zu sparen, eine ausgeglichene Suchbaum, in dem jeder Eintrag statt einer verknüpften Liste, für eine bessere Leistung.

Die Raum-versierte, aber immer noch sehr schnell-Lösung: TRIE variation

Diese Lösung verwendet die folgende Beobachtung:

Wenn die'? ' - Zeichen am Ende des Wortes, trie wäre das eine gute Lösung.

Die Suche im trie suchen würde, an der Länge des Wortes, und für die letzten paar Buchstaben, eine DFS-Traversierung bringen würde, alle Endungen.
Sehr schnell, und sehr Speicher-versierte Lösung.

So können nutzen diese Beobachtung, um etwas zu bauen, zu arbeiten, genau wie diese.

Kann man darüber nachdenken, jedes Wort, das Sie in dem Wörterbuch, wie ein Wort endet mit @ (oder jedes andere symbol, das nicht vorhanden ist in deinem Wörterbuch).
So ist das Wort 'space' wäre 'space@'.
Nun, wenn Sie drehen Sie jedes der Wörter, die mit dem ' @ ' - Zeichen, erhalten Sie die folgende:

space@, pace@s, ace@sp, *ce@spa*, e@spac

(kein @ als ersten Buchstaben).

Wenn Sie alle diese Varianten in einem TRIE, können Sie problemlos das Wort finden Sie suchen bei der Länge des Wortes, durch 'drehen' zu deinem Wort.

Beispiel:
Sie möchten herausfinden, alle Wörter, die fit 's??ce' (einer von Ihnen ist der Raum, der andere ist Scheibe).
Sie bauen das Wort: s??ce@, und drehen Sie es so, dass die ? Zeichen ist am Ende. d.h. 'ce@s -??'

Alle von der rotation Variationen gibt es in der Marina, und insbesondere 'ce@spa' (die mit * gekennzeichneten oben). Nachdem der Anfang gefunden ist - Sie müssen gehen über alle Fortsetzungen in die Länge zu, und speichern Sie Sie. Dann müssen Sie, um Sie zu drehen, wieder so, dass die @ ist der Letzte Brief, und walla - Sie haben alle Begriffe, die Sie gesucht haben!

Fazit dieser Lösung:

• Speicherverbrauch:
  Für jedes Wort, alle seine Rotationen erscheinen in der Marina. Durchschnittlich *6 von der Größe des Speichers gespeichert ist, in der trie. Die trie Größe *3 (nur geraten...) der Raum gespeichert drin. So die insgesamt notwendigen Raum für diese versuche ist 6*3*100,000 = ist 1.800.000 Wörter ~= 6.8 mega-Byte.

• Zeit für jede Suche:

  • drehen des Wortes: O(word length)
  • Suche, die Ihren Anfang in der Marina: O(word length)
  • gehen über alle von den Endungen: O(Anzahl der Treffer)
  • drehen der enden: O(Gesamtlänge der Antworten)

  Zusammenfassend, es ist sehr sehr schnell, und hängt von der Wortlänge * kleine Konstante.

Zusammenfassend...

Die zweite Wahl, hat eine gute Zeit/Platz-Komplexität und wäre die beste option für Sie zu verwenden. Es gibt ein paar Probleme mit der zweiten Lösung (in diesem Fall möchten Sie vielleicht die Verwendung der ersten Lösung):

• Komplexer zu implementieren. Ich bin mir nicht sicher, ob es Programmiersprachen mit versucht, integrierte out of the box. Wenn es nicht - es bedeutet, dass müssen Sie es selbst implementieren...
• Nicht gut skalieren. Wenn Sie morgen entscheiden, dass Sie brauchen, Ihr Fragezeichen zu verbreiten alle über das Wort, und nicht unbedingt miteinander verbunden, Sie müssen schwer glauben, wie fit die zweite Lösung. Im Fall der ersten Lösung - es ist ganz einfach, zu verallgemeinern.

Directed Acyclic Word Graph wäre die perfekte Datenstruktur für dieses problem. Es kombiniert die Effizienz eines trie (trie kann gesehen werden als ein Spezialfall der DAWG), aber viel mehr Platz effiziente. Typische DAWG nehmen Bruchteil der Größe, die nur-text-Datei mit dem Worte nehmen würde.

Aufzählen von Wörtern, die bestimmte Bedingungen erfüllen ist einfach und das gleiche wie in trie - Sie müssen durch den Graphen depth-first-Mode.

Als erstes benötigen wir eine Möglichkeit zum Vergleich der query-string mit einem bestimmten Eintrag. Nehmen wir an, eine Funktion mit regexes: matches(query,trialstr).

Einen O(n) Algorithmus wäre zu einfach verlaufen durch jeden Punkt der Liste (Wörterbuch vertreten sein werden als Liste in das Programm), Vergleich der einzelnen, um Ihre Abfrage-string.

Mit ein wenig pre-Berechnung, die Sie verbessern könnte dieses für eine große Anzahl von Abfragen durch den Bau einer zusätzlichen Liste der Wörter für jeden Buchstaben, so dass Ihr Wörterbuch Aussehen könnte:

wordsbyletter = { 'a' : ['aardvark', 'abacus', ... ],
                  'b' : ['bat', 'bar', ...],
                  .... }

Dies wäre jedoch nur von begrenztem nutzen, insbesondere, wenn Ihre query-string beginnt mit einem unbekannten Charakter. So können wir noch besser machen mit der Feststellung, wo Sie bei einem bestimmten Wort einen bestimmten Buchstaben liegt, generieren:

wordsmap = { 'a':{ 0:['aardvark', 'abacus'],
                   1:['bat','bar'] 
                   2:['abacus']},
             'b':{ 0:['bat','bar'],
                   1:['abacus']},
             ....
           }

Wie Sie sehen können, ohne mit Indizes, Sie werden am Ende enorm die Erhöhung der Menge des benötigten Speicherplatzes - jedoch speziell ein Wörterbuch mit n Wörtern und Durchschnittliche Länge m benötigen nm² Stauraum. Allerdings könnte man jetzt sehr schnell tun, Ihr Aussehen, bis man alle Wörter von jedem Satz, die mithalten können.

Die endgültige Optimierung (die Sie nutzen könnten, von der Fledermaus auf den naiven Ansatz) ist auch eine Trennung aller Wörter der gleichen Länge in separaten Läden, da Sie immer wissen, wie lange das Wort ist.

Diese version wäre O(kx), wo k die Nummer von bekannte Briefe in die Abfrage Wort, und x=x(n) ist die Zeit zu schauen, bis ein einzelnes Element in einem Wörterbuch der Länge n in Ihrer Umsetzung (in der Regel log(n).

Also mit einer endgültigen Wörterbuch wie:

allmap = { 
           3 : { 
                  'a' : {
                          1 : ['ant','all'],
                          2 : ['bar','pat']
                         }
                  'b' : {
                          1 : ['bar','boy'],
                      ...
                }
           4 : {
                  'a' : {
                          1 : ['ante'],
                      ....

Dann unser Algorithmus ist einfach:

possiblewords = set()
firsttime = True
wordlen = len(query)
for idx,letter in enumerate(query):
    if(letter is not '?'):
        matchesthisletter = set(allmap[wordlen][letter][idx])
        if firsttime:
             possiblewords = matchesthisletter
        else:
             possiblewords &= matchesthisletter

Am Ende, der Satz possiblewords enthält all die passenden Buchstaben.

Nehme an, Sie haben genügend Speicherplatz, man konnte bauen ein Riesen-hashmap, um die Antwort in konstanter Zeit. Hier ist ein kurzes Beispiel in python:

from array import array
all_words = open("english-words").read().split()
big_map = {}

def populate_map(word):
  for i in range(pow(2, len(word))):
    bin = _bin(i, len(word))
    candidate = array('c', word)
    for j in range(len(word)):
      if bin[j] == "1":
        candidate[j] = "?"
    if candidate.tostring() in big_map:
      big_map[candidate.tostring()].add(word)
    else:
      big_map[candidate.tostring()] = set([word])

def _bin(x, width):
    return ''.join(str((x>>i)&1) for i in xrange(width-1,-1,-1))

def run():
  for word in all_words:
    populate_map(word)

run()

>>> big_map["y??r"]
set(['your', 'year'])
>>> big_map["yo?r"]
set(['your'])
>>> big_map["?o?r"]
set(['four', 'poor', 'door', 'your', 'hour'])

Bauen Sie ein hash-set von all den Worten. Zu finden passt, ersetzen Sie die Fragezeichen im Muster, bei dem jede mögliche Kombination von Buchstaben. Wenn es zwei Fragezeichen, eine Abfrage besteht aus 26² = 676 schnelle, Konstante erwartete-Zeit-hash-table-lookups.

import itertools

words = set(open("/usr/share/dict/words").read().split())

def query(pattern):
    i = pattern.index('?')
    j = pattern.rindex('?') + 1
    for combo in itertools.product('abcdefghijklmnopqrstuvwxyz', repeat=j-i):
        attempt = pattern[:i] + ''.join(combo) + pattern[j:]
        if attempt in words:
            print attempt

Diese verbraucht weniger Speicher als meine andere Antwort, aber wird es exponentiell langsamer, da Sie mehr Fragezeichen.

Eine regex-basierte Lösung betrachten jeden möglichen Wert in Ihrem Wörterbuch. Wenn die Leistung ist die größte Einschränkung, ein index gebaut werden konnte, um ihn zu beschleunigen erheblich.

Könnten Sie beginnen mit einem index auf jedes Wort der Länge enthält einen index jeder index=Charakter entsprechenden Wort-Sätze. Für die Länge von 5 Wörtern, zum Beispiel 2=r : {write, wrote, drate, arete, arite}, 3=o : {wrote, float, group} usw. Um die möglichen übereinstimmungen für die ursprüngliche Abfrage, sagen '?ro??', das Wort setzt wäre durchschnitten was in {wrote, group} in diesem Fall.

Dies ist unter der Annahme, dass das nur Platzhalter, wird ein einzelnes Zeichen, und dass die Wortlänge bekannt vor. Wenn diese ungültig sind Annahmen, kann ich nur empfehlen, n-Gramm-basierte text-matching, wie besprochen, in dieses Papier.

Haben Sie sich überlegt mit einem Ternäre Suche Baum?
Die lookup-Geschwindigkeit ist vergleichbar mit einem versuchten, aber es ist mehr Platz-effizient.

Habe ich implementiert diese Datenstruktur mehrere Male, und es ist eine ziemlich einfache Aufgabe in den meisten Sprachen.

Hier ist, wie ich es tun würde:

1. Verketten Sie die Wörter des Wörterbuchs in eine lange Zeichenfolge, getrennt durch eine nicht-Wort-Zeichen.
2. Setzen Sie alle Wörter in eine TreeMap, wo der Schlüssel ist das Wort und der Wert ist der offset, der den Anfang des Wortes in den großen String.
3. Finden der Basis der such-string, d.h. die größten und führenden Teilzeichenfolge, die enthalten nicht -'?'.
4. Verwenden TreeMap.higherKey(base) und TreeMap.lowerKey(next(base)) zu finden, wird der Bereich innerhalb der Zeichenfolge zwischen die matches werden gefunden. (Die next Methode muss zur Berechnung der nächsten größeren Wort, um die Basis-Zeichenfolge mit der gleichen Anzahl oder weniger Zeichen; z.B. next("aa") ist "ab", next("az") ist "b".)
5. Erstellen eines regex für den Suchbegriff, und verwenden Sie Matcher.find() zu suchen, die Teilstrings entsprechend zu dem Bereich.

Schritte 1 und 2 sind vorher getan was eine Daten-Struktur mit der O(NlogN) Raum, wo N ist die Anzahl der Wörter.

Dieser Ansatz verkommt zu einer brute-force-regex-Suche von das gesamte Wörterbuch, wenn die '?' erscheint in der ersten position, aber je weiter rechts es liegt, desto weniger übereinstimmende getan werden muss.

BEARBEITEN:

Zur Verbesserung der performance in dem Fall, wo '?' ist das erste Zeichen, erstellen Sie eine sekundäre lookup-Tabelle, die Datensätze der start - /Ende-offsets der läuft von Worten, deren zweites Zeichen 'a', 'b', und so weiter. Dies kann verwendet werden, in dem Fall, wo die erste nicht-'?' ist der zweite Charakter. Sie können uns eine ähnliche Vorgehensweise für Fälle, in denen der erste nicht-'?' ist das Dritte Zeichen, der vierte Charakter und so weiter, aber Sie am Ende mit größeren und größeren Zahl von kleineren und kleinere Auflagen, und schließlich diese "Optimierung" wird unwirksam.

Einen alternativen Ansatz, der erfordert deutlich mehr Platz, aber der ist schneller in den meisten Fällen ist die Vorbereitung der dictionary-Datenstruktur, wie Sie oben für alle Drehungen der Wörter im Wörterbuch. Zum Beispiel, die erste Drehung, die würde darin bestehen, alle Worte, 2 Zeichen oder mehr mit dem ersten Zeichen des Wortes verschoben, um das Ende des Wortes. Die zweite rotation wäre Worte mit 3 Zeichen oder mehr mit den ersten beiden Zeichen verschoben an das Ende, und so weiter. Dann führen Sie die Suche, suchen Sie nach dem längste Folge von nicht -'?' - Zeichen im Suchtext. Wenn der index des ersten Zeichens dieser Teilstring N verwenden Sie die Nth rotation zu finden, das reicht, und die Suche in der N-TEN Drehung word-Liste.

Zusammenfassung: Verwenden Sie zwei compact-binary-gesucht-Indizes, eines der Worte, und eine der Umgekehrt Worte. Der Raum kostet ist 2N Zeiger, die Indizes, fast alle Suchvorgänge sehr schnell gehen; der Schlimmste Fall "??e", ist immer noch anständig. Wenn Sie separate Tabellen für jedes Wort der Länge, das würde selbst dem schlimmsten Fall sehr schnell.

Details: Stephen C. geschrieben, eine gute Idee,: suchen Sie eine geordnete Wörterbuch zu finden, den Bereich, wo das Muster erscheinen kann. Dies hilft nicht, wenn das Muster startet mit einer wildcard. Sie könnten auch den index von word-Länge, aber hier ist eine andere Idee: hinzufügen eines geordneten index, der die Umgekehrt Wörterbuch; dann ein Muster bringt immer einen kleinen Bereich in entweder der vorwärts-index oder umgekehrter-Wort-index (da wir gerade gesagt, es gibt keine Muster, wie ?ABCD?). Die Worte selbst müssen nur einmal gespeichert, wobei die Einträge der beiden Strukturen zeigen auf den selben Worten, und die lookup-Verfahren können Sie entweder vorwärts oder rückwärts; aber die Verwendung von Python die built-in-binary-search-Funktion, die ich gemacht habe, zwei separate Zeichenfolgen-arrays stattdessen verschwenden Platz. (Ich bin mit einem sortierten array statt einem Baum, wie andere vorgeschlagen haben, da es Platz spart und geht mindestens genauso schnell.)

Code:

import bisect, re

def forward(string): return string
def reverse(string): return string[::-1]

index_forward = sorted(line.rstrip('\n')
                       for line in open('/usr/share/dict/words'))
index_reverse = sorted(map(reverse, index_forward))

def lookup(pattern):
    "Return a list of the dictionary words that match pattern."
    if reverse(pattern).find('?') <= pattern.find('?'):
        key, index, fixup = pattern, index_forward, forward
    else:
        key, index, fixup = reverse(pattern), index_reverse, reverse
    assert all(c.isalpha() or c == '?' for c in pattern)
    lo = bisect.bisect_left(index, key.replace('?', 'A'))
    hi = bisect.bisect_right(index, key.replace('?', 'z'))
    r = re.compile(pattern.replace('?', '.') + '$')
    return filter(r.match, (fixup(index[i]) for i in range(lo, hi)))

Tests: (Der code funktioniert auch für Muster, wie ?AB?D?, allerdings ohne die Geschwindigkeit zu garantieren.)

>>> lookup('hello')
['hello']
>>> lookup('??llo')
['callo', 'cello', 'hello', 'uhllo', 'Rollo', 'hollo', 'nullo']
>>> lookup('hel??')
['helio', 'helix', 'hello', 'helly', 'heloe', 'helve']
>>> lookup('he?l')
['heal', 'heel', 'hell', 'heml', 'herl']
>>> lookup('hx?l')
[]

Effizienz: Diese Bedürfnisse 2N Zeiger plus den erforderlichen Speicherplatz zum speichern der Wörterbuch-word-text (die getunte version). Das worst-case-Zeit kommt auf das Muster"??e' die Blicke an 44062 Kandidaten in meinem 235k-word /usr/share/dict/words; aber fast alle Abfragen sind wesentlich schneller, wie 'h??lo " ein Blick auf 190, und die Indizierung zunächst auf Wort-Länge reduzieren würde '??e' fast zu nichts, wenn wir müssen. Jede Kandidaten-check geht schneller als die hashtable-lookups andere vorgeschlagen haben.

Ähnelt dem Rotationen-index Lösung, die verhindert, alle false-match-Kandidaten auf Kosten des Müssens über 10N Zeigern anstelle von 2N (angenommen, dass eine Durchschnittliche Wortlänge von etwa 10, wie in meiner /usr/share/dict/words).

Könnten Sie tun, ein einzelnes binary search pro Suche, anstelle von zwei, mit einem benutzerdefinierten such-Funktion sucht nach nieder-gebunden und high-gebunden zusammen (so der gemeinsame Teil der Suche nicht wiederholt).

Wenn Sie ernsthaft wollen, etwas in der Größenordnung von einer Milliarde Suchanfragen pro Sekunde (obwohl ich nicht davon träumen, warum jemand außerhalb von jemandem machen, der nächste grand-master-scrabble AI oder etwas für eine riesige web-service wollen, dass schnell), ich empfehle die Verwendung threading, um zu laichen [Anzahl der Kerne auf deine Maschine] threads + einem master-thread, dass die Delegierten die Arbeit auf alle threads. Wenden Sie dann die beste Lösung, die Sie bis jetzt gefunden habe und hoffe, dass Sie don ' T run out of memory.

Eine Idee, die ich hatte, ist, dass Sie beschleunigen einigen Fällen durch die Zubereitung in Scheiben geschnitten unten Wörterbücher per Brief, dann, wenn Sie wissen, die ersten Buchstaben der Auswahl, können Sie resort zu suchen in einem viel kleineren Heuhaufen.

Ein anderer Gedanke, den ich hatte, war, dass Sie versuchten, um brute-force etwas -- vielleicht Baue eine DB oder Liste oder so für scrabble?