<user input> で始まる辞書内のすべての単語をリストします。

https://stackoverflow.com/questions/112532

02-07-2019
|

質問

ユーザーが文字列を入力すると、その文字列で始まる単語のリストが生成されるプログラムを作成するにはどうすればよいでしょうか?

元：
ユーザー：「アブド」
プログラム: 放棄、腹部、誘拐...

ありがとう！

編集：私は Python を使用していますが、これは言語にかなり依存しない問題だと思います。

解決

debian[のような]マシンを使用している場合は、

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

私のP200では0.040秒すべてがかかります。

他のヒント

使う試してみる.

単語のリストをトライに追加します。ルートからリーフまでの各パスは有効な単語です。ルートから中間ノードへのパスはプレフィックスを表し、中間ノードの子はプレフィックスの有効な補完です。

これを行うための最良の方法の 1 つは、有向グラフを使用して辞書を保存することです。セットアップには少し時間がかかりますが、一度セットアップが完了すると、今話しているような検索を行うのは非常に簡単です。

グラフ内のノードは単語の文字に対応するため、各ノードには 1 つの受信リンクと最大 26 (英語) の送信リンクがあります。

辞書を含む並べ替えられたリストを維持し、有向グラフを辞書のインデックスとして使用するハイブリッドアプローチを使用することもできます。次に、有向グラフで接頭辞を検索し、辞書のその点に移動して、検索条件に一致するすべての単語を吐き出します。

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

ああ、Python の編集は見ませんでした。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]

本当に速度が必要な場合は、トライ/オートマトンを使用してください。ただし、単語のリストがソートされている場合、単純にリスト全体をスキャンするよりも高速になります。

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

オートマトンは辞書のサイズに関しては O(1) ですが、このアルゴリズムは実際に接頭辞で始まる文字列の数に関しては O(log(m)) の次に O(n) であることに注意してください。フルスキャンは O(m) で、n << m です。

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)

本当に効率を上げたい場合は、接尾辞ツリーまたは接尾辞配列を使用してください。ウィキペディアの記事.

あなたの問題は、接尾辞ツリーが何を処理するように設計されているかです。Python の実装もあります - ここ

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

正規表現を使用して単語のリストを検索してみてください。/^word/ と一致するものをすべて報告します。

必要がある場合は、 本当に 早速、ツリーを使ってみましょう。

配列を作成し、最初の文字に基づいて単語を 26 セットに分割し、次に 2 番目の文字に基づいて各項目を 26 に分割し、さらに再度分割します。

したがって、ユーザーが「abd」と入力すると、Array[0][1][3] を検索し、そのように始まるすべての単語のリストを取得します。この時点で、リストはクライアントに渡して JavaScript を使用してフィルタリングできるほど小さいものになっているはずです。

最も Python 的なソリューション

# 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

ジェネレーターは 1 回しか使用できないので、複数回使用する場合は、リストに変換するか (list(word_generator) を使用)、itertools.tee 関数を使用してください。

最良の方法:

それをデータベースに保存し、SQL を使用して必要な単語を検索します。辞書にたくさんの単語が含まれている場合、辞書ははるかに速く効率的になります。

Python には、仕事の実行に役立つ何千もの DB API が用意されています ;-)

使用できます str.startswith(). 。公式ドキュメントへの記録:

str.startswith(prefix[, start[, end]])

文字列がプレフィックスで始まる場合は True を返し、それ以外の場合は False を返します。prefix は、検索するプレフィックスのタプルにすることもできます。オプションの start を使用すると、その位置から始まる文字列をテストします。オプションの end を指定すると、その位置で文字列の比較を停止します。

以下のように:

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

辞書が非常に大きい場合は、Python テキストインデックスを使用してインデックスを作成することをお勧めします (PyLucene - lucene に Python 拡張機能を使用したことがないことに注意してください)。検索は効率的で、検索の「スコア」を返すこともできます。

また、辞書が比較的静的であれば、インデックスを頻繁に再作成するオーバーヘッドも発生しません。

ハエを殺すためにバズーカを使用しないでください。SQLite のような単純なものを使用してください。すべての最新言語に必要なツールがすべて揃っており、次のことを行うだけで済みます。

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

それは電光石火の速さで、赤ちゃんでもできます。さらに、移植可能で永続的であり、メンテナンスが非常に簡単です。

Python のチュートリアル:

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

リニアスキャンは遅いですが、プレフィックスツリーはおそらく過剰です。単語を並べ替えたままにし、二分検索を使用するのが、迅速かつ簡単な妥協策です。

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']

単語を .csv ファイルに保存すると、pandas を使用してこれをかなりきれいに解決できます。ユーザーがセッションごとに複数の検索を実行できる必要がある場合は、一度読み取った後、すでにロードされているデータフレームを再利用できます。。

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

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow