Répertoriez tous les mots d'un dictionnaire commençant par < saisie utilisateur >

Question

Comment créer un programme dans lequel l'utilisateur entre une chaîne, et le programme génère une liste de mots commençant par cette chaîne?

Ex:
Utilisateur: " abd "
Programme: abdiquer, abdomen, enlèvement ...

Merci!

Éditer: J'utilise python, mais je suppose qu'il s'agit d'un problème relativement indépendant du langage.

Answer 1

Si vous êtes sur une machine debian,

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

prend tous les 0.040s sur mon P200.

Answer 2

Utilisez un trie .

Ajoutez votre liste de mots à un trie. Chaque chemin de la racine à une feuille est un mot valide. Un chemin allant de la racine à un noeud intermédiaire représente un préfixe et les enfants du noeud intermédiaire sont des complétions valides pour le préfixe.

Answer 3

L’un des meilleurs moyens de le faire consiste à utiliser un graphique dirigé pour stocker votre dictionnaire. Il faut un peu de préparation, mais une fois cela fait, il est assez facile de faire le type de recherche dont vous parlez.

Les nœuds du graphique correspondent à une lettre dans votre mot. Chaque nœud aura donc un lien entrant et un maximum de 26 liens sortants (en anglais).

Vous pouvez également utiliser une approche hybride dans laquelle vous maintenez une liste triée contenant votre dictionnaire et utilisez le graphe dirigé en tant qu’index dans votre dictionnaire. Ensuite, il vous suffit de rechercher votre préfixe dans le graphique que vous dirigez, puis d'aller à cet endroit dans votre dictionnaire et de recracher tous les mots correspondant à vos critères de recherche.

Answer 4

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

oh je n'ai pas vu l'édition Python, voici la même chose en 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

Si vous voulez vraiment de la vitesse, utilisez un tri / automate. Cependant, quelque chose sera plus rapide que de simplement parcourir toute la liste, étant donné que la liste de mots est triée:

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

Notez qu'un automate est O (1) en ce qui concerne la taille de votre dictionnaire, alors que cet algorithme est O (log (m)), puis O (n) en ce qui concerne le nombre de chaînes qui commencent réellement par le préfixe, alors que le scan complet est O (m), avec 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

Si vous voulez vraiment être efficace, utilisez des arbres de suffixes ou des tableaux de suffixes - article de wikipedia .

Votre problème est ce que les arbres de suffixes ont été conçus pour gérer. Il existe même une implémentation pour Python - ici

Answer 8

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

Answer 9

Essayez d’utiliser regex pour parcourir votre liste de mots, par exemple. / ^ word / et signale toutes les correspondances.

Answer 10

Si vous devez être vraiment rapide, utilisez un arbre:

Créez un tableau et divisez les mots en 26 ensembles en fonction de la première lettre, puis divisez chaque élément en 26 en fonction de la deuxième lettre, puis à nouveau.

Donc, si votre utilisateur tape " abd " vous chercheriez Array [0] [1] [3] et obtiendriez une liste de tous les mots commençant comme ça. À ce stade, votre liste devrait être suffisamment petite pour être transmise au client et utiliser le javascript pour filtrer.

Answer 11

La plupart des solutions Pythonic

# 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

N'oubliez pas que les générateurs ne peuvent être utilisés qu'une seule fois. Réglez-le ainsi (utilisez list (word_generator)) ou utilisez la fonction itertools.tee si vous prévoyez de l'utiliser plusieurs fois.

Meilleur moyen de le faire:

Stockez-le dans une base de données et utilisez SQL pour rechercher le mot dont vous avez besoin. S'il y a beaucoup de mots dans votre dictionnaire, ce sera beaucoup plus rapide et efficace.

Python a reçu des milliers d’API de base de données pour vous aider à faire le travail ;-)

Answer 12

Vous pouvez utiliser str.startswith () . enregistrement dans les documents officiels:

str.startswith (préfixe [, début [, fin]])

Renvoie True si la chaîne commence par le préfixe, sinon renvoie False. préfixe peut également être un tuple de préfixes à rechercher. Avec l'option optionnelle start, testez la chaîne commençant à cette position. Avec facultatif end, arrêtez de comparer la chaîne à cette position.

comme ci-dessous:

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

Answer 13

Si votre dictionnaire est vraiment volumineux, je suggérerais d'indexer avec un index de texte en python (PyLucene - notez que je n'ai jamais utilisé l'extension python pour lucene). La recherche serait efficace et vous pourriez même renvoyer un résultat de recherche. '.

En outre, si votre dictionnaire est relativement statique, vous n'aurez même pas souvent à supporter l'indexation.

Answer 14

N'utilisez pas de bazooka pour tuer une mouche. Utilisez quelque chose de simple, tout comme SQLite. Il existe tous les outils dont vous avez besoin pour toutes les langues modernes et vous pouvez simplement le faire:

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

Il est rapide comme l'éclair et un bébé pourrait le faire. De plus, il est portable, persistant et facile à entretenir.

tuto python:

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

Answer 15

Un balayage linéaire est lent, mais un arbre de préfixes est probablement excessif. Garder les mots triés et utiliser une recherche binaire est un compromis simple et rapide.

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

Si vous stockez les mots dans un fichier .csv, vous pouvez utiliser des pandas pour résoudre ce problème de manière assez nette. Une fois que vous l'avez lu, vous pouvez réutiliser le bloc de données déjà chargé si l'utilisateur doit pouvoir en exécuter plus d'un. recherche par session.

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