Liste aller Wörter in einem Wörterbuch, das mit starten

Question

Wie würde eine gehen über ein Programm zu machen, wo der Benutzer eine Zeichenfolge eingibt, und das Programm generiert eine Liste von Worten mit dieser Zeichenkette beginnen?

Ex:
Benutzer: "abd"
Programm: abdicate, Bauch, verschleppen ...

Danke!

---

Edit: Ich verwende Python, aber ich nehme an, dass dies ein ziemlich sprachunabhängige Problem ist,

.

Answer 1

Wenn Sie auf einer debian [-ähnlichen] Maschine,

#!/bin/bash
echo -n "Enter a word: "
read input
grep "^$input" /usr/share/dict/words

nimmt alle 0.040s auf meinem P200.

Answer 2

Verwenden Sie einen trie .

Fügen Sie Ihre Liste von Wörtern zu einem Trie. Jeder Pfad von der Wurzel zu einem Blatt ist ein gültiges Wort. Ein Weg von einer Wurzel zu einem Zwischenknoten stellt einen Präfix und die Kinder des Zwischenknotens gilt für die Beendigungen Präfix.

Answer 3

Einer der besten Wege, dies zu tun ist, einen gerichteten Graphen zu verwenden, Ihr Wörterbuch zu speichern. Es dauert ein wenig einrichten, aber einmal erledigt es ziemlich einfach ist, dann die Art der Suche zu tun über Sie sprechen.

Die Knoten des Graphen entsprechen einen Brief in Ihrem Wort, so dass jeder Knoten eine eingehende Verbindung und bis zu 26 (in englischer Sprache) ausgehende Links.

Sie können auch einen hybriden Ansatz verwenden, in dem Sie eine sortierte Liste mit Ihrem Wörterbuch erhalten und die gerichteten Graphen als Index in Ihr Wörterbuch verwenden. Dann einfach Sie Ihren Präfix in Ihrem gerichteten Graphen sucht und dann zu diesem Punkt in Ihrem Wörterbuch geht und ausspucken alle Worte Ihre Suchkriterien entsprechen.

Answer 4

egrep `read input && echo ^$input` /usr/share/dict/words

oh ich nicht der Python bearbeitet gesehen habe, hier ist die gleiche Sache in Python

my_input = raw_input("Enter beginning of word: ")
my_words = open("/usr/share/dict/words").readlines()
my_found_words = [x for x in my_words if x[0:len(my_input)] == my_input]

Answer 5

Wenn Sie wirklich Geschwindigkeit wollen, verwenden Sie einen Trie / Automaten. Aber etwas, das schneller als einfaches Scannen die gesamte Liste sein wird, da die Liste der Wörter wird sortiert:

from itertools import takewhile, islice
import bisect

def prefixes(words, pfx):
    return list(
             takewhile(lambda x: x.startswith(pfx), 
                       islice(words, 
                              bisect.bisect_right(words, pfx), 
                              len(words)))

Beachten Sie, dass ein Automat O (1) in Bezug auf die Größe des Wörterbuchs ist, während dieser Algorithmus O (log (m)) und dann O (n) in Bezug auf die Anzahl der Strings, die tatsächlich mit dem ist beginnen prefix, während die Scan O (m), mit n << m.

Answer 6

def main(script, name):
    for word in open("/usr/share/dict/words"):
        if word.startswith(name):
            print word,

if __name__ == "__main__":
    import sys
    main(*sys.argv)

Answer 7

Wenn Sie wirklich effizient sein wollen - Verwendung Suffix Bäume oder Suffixarray - Wikipedia-Artikel .

Ihr Problem ist, welche Suffix Bäume wurden entwickelt, zu handhaben. Es gibt sogar Implementierung für Python - hier

Answer 8

var words = from word in dictionary
            where word.key.StartsWith("bla-bla-bla");
            select word;

Answer 9

Versuchen regex durch die Liste von Wörtern zu suchen, zum Beispiel / ^ Wort / und berichten alle Spiele.

Answer 10

Wenn Sie auf wirklich schnell, verwenden Sie einen Baum:

ein Array erstellen und teilen Sie die Wörter in 26 Sätzen auf den ersten Buchstaben basiert, spaltete dann jedes Element in 26 basierend auf den zweiten Buchstaben, dann wieder.

Also, wenn Ihr Benutzertyp „abd“ Sie Array aussehen würden [0] [1] [3] und erhält eine Liste aller Worte wie das Start. An diesem Punkt der Liste sollte klein genug sein, um den Client zu übergehen und Javascript verwenden zu filtern.

Answer 11

Die meisten Pythonic Lösung

# set your list of words, whatever the source
words_list = ('cat', 'dog', 'banana')
# get the word from the user inpuit
user_word = raw_input("Enter a word:\n")
# create an generator, so your output is flexible and store almost nothing in memory
word_generator = (word for word in words_list if word.startswith(user_word))

# now you in, you can make anything you want with it 
# here we just list it :

for word in word_generator :
    print word

Denken Sie daran, Generatoren können nur einmal verwendet werden, so schalten Sie ihn in eine Liste (mit Liste (word_generator)) oder die itertools.tee Funktion verwenden, wenn Sie es erwarten mit als einmal.

Der beste Weg, es zu tun:

Speichern Sie sie in eine Datenbank und verwenden SQL für das Wort suchen Sie benötigen. Wenn es viele Wörter in Ihrem Wörterbuch ist, wird es viel schneller und effizienter sein.

Python bekam tausend von DB-API Sie tun, um die Arbeit zu helfen; -)

Answer 12

Sie können str.startswith() verwenden. Aufnahme in der offiziellen Dokumentation:

str.startswith (Präfix [, Start [, end]])

return true, wenn der String mit dem Präfix beginnt, sonst return false. Präfix kann auch ein Tupel von Präfixen sein zu suchen. Mit optionalem Start, beginnend Test-String an dieser Position. Mit optionalem Ende, Stopp-String an dieser Position verglichen wird.

wie folgt:

user_input = input('Enter something: ')
for word in dictionary:
    if str.startswith(user_input):
        return word

Answer 13

Wenn Ihr Wörterbuch ist wirklich groß, ich Indizierung mit einem Python-Textindex würde vorschlagen (PyLucene - beachten Sie, dass ich habe nie die Python-Erweiterung für Lucene verwendet) Die Suche effizient wäre und man konnte sogar eine Suche ‚Partitur zurückzukehren ‘.

Auch, wenn Ihr Wörterbuch relativ statisch ist, werden Sie nicht einmal den Aufwand für Neuindexierung haben sehr oft.

Answer 14

Verwenden Sie keine Bazooka eine Fliege zu töten. Verwenden Sie etwas Einfaches wie SQLite. Es sind alle Werkzeuge, die Sie für alle modernen Sprachen benötigen und Sie können einfach tun:

"SELECT word FROM dict WHERE word LIKE "user_entry%"

Es ist blitzschnell und ein Baby könnte es tun. Was mehr ist, es ist tragbar, hartnäckig und so leicht zu pflegen.

Python tuto:

http://www.initd.org/pub /software/pysqlite/doc/usage-guide.html

Answer 15

Eine lineare Scan ist langsam, aber ein Präfix-Baum ist wahrscheinlich übertrieben. Halten Sie die Worte, sortierten und mit einer binären Suche ist ein schneller und einfacher Kompromiss.

import bisect
words = sorted(map(str.strip, open('/usr/share/dict/words')))
def lookup(prefix):
    return words[bisect.bisect_left(words, prefix):bisect.bisect_right(words, prefix+'~')]

>>> lookup('abdicat')
['abdicate', 'abdication', 'abdicative', 'abdicator']

Answer 16

Wenn Sie die Worte in einer CSV-Datei speichern, können Sie Pandas, dies zu lösen ziemlich ordentlich, und nachdem Sie es gelesen haben, wenn Sie den bereits geladenen Datenrahmen wiederverwendet werden können, wenn der Benutzer in der Lage ist mehr als ein durchzuführen Suche pro Sitzung.

df = pd.read_csv('dictionary.csv')
matching_words = df[0].loc[df[0].str.startswith(user_entry)]