ユーザーが文字列を入力し、プログラムがその文字列で始まる単語のリストを生成するプログラムを作成するにはどうすればよいでしょうか。
例：
ユーザー：「abd」
プログラム：abdicate、abdomen、abduct .. ..
ありがとう！
編集：私はPythonを使用していますが、これはかなり言語に依存しない問題だと思います。
6852 次
16 に答える
11
トライを使用します。
単語リストをトライに追加します。ルートからリーフへの各パスは有効な単語です。ルートから中間ノードへのパスはプレフィックスを表し、中間ノードの子はプレフィックスの有効な補完です。
于 2008-09-21T23:35:48.210 に答える
8
これを行う最善の方法の 1 つは、有向グラフを使用して辞書を格納することです。設定には少し時間がかかりますが、設定が完了すると、話しているタイプの検索を行うのはかなり簡単です。
グラフのノードは単語の文字に対応するため、各ノードには 1 つの受信リンクと最大 26 (英語) の送信リンクがあります。
辞書を含む並べ替えられたリストを維持し、有向グラフを辞書へのインデックスとして使用するハイブリッド アプローチを使用することもできます。次に、有向グラフでプレフィックスを検索し、辞書のそのポイントに移動して、検索条件に一致するすべての単語を吐き出します。
于 2008-09-21T23:35:09.600 に答える
6
debian[-like] マシンを使用している場合、
#!/bin/bash
echo -n "Enter a word: "
read input
grep "^$input" /usr/share/dict/words
私の P200 では 0.040 秒すべてかかります。
于 2008-09-21T23:37:53.133 に答える
4
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]
于 2008-09-21T23:50:59.810 に答える
4
本当にスピードが必要な場合は、トライ/オートマトンを使用してください。ただし、単語のリストがソートされていることを考えると、単にリスト全体をスキャンするよりも高速になるものがあります。
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 です。
于 2008-09-21T23:57:05.740 に答える
2
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)
于 2008-09-21T23:35:07.493 に答える
2
本当に効率的になりたい場合は、接尾辞ツリーまたは接尾辞配列を使用してください -ウィキペディアの記事。
あなたの問題は、サフィックスツリーが処理するように設計されたものです。Python の実装もあります - here
于 2008-09-21T23:36:31.000 に答える
1
ほとんどの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
ジェネレーターは1回しか使用できないため、リストに変換するか（list（word_generator）を使用）、複数回使用する場合はitertools.tee関数を使用してください。
それを行うための最良の方法：
それをデータベースに保存し、SQLを使用して必要な単語を探します。辞書にたくさんの単語がある場合、それははるかに速くて効率的です。
Pythonはあなたが仕事をするのを助けるために何千ものDBAPIを手に入れました;-)
于 2008-11-21T11:11:41.757 に答える
1
var words = from word in dictionary
where word.key.StartsWith("bla-bla-bla");
select word;
于 2008-09-21T23:29:51.063 に答える
1
正規表現を使用して単語のリスト（たとえば/ ^ word /）を検索し、すべての一致を報告してみてください。
于 2008-09-21T23:30:13.777 に答える
1
本当に高速にする必要がある場合は、ツリーを使用します。
配列を作成し、最初の文字に基づいて単語を 26 セットに分割し、次に 2 番目の文字に基づいて各項目を 26 に分割し、再度分割します。
したがって、ユーザーが「abd」と入力すると、Array[0][1][3] を探して、そのように始まるすべての単語のリストを取得します。その時点で、リストはクライアントに渡され、javascript を使用してフィルタリングするのに十分なほど小さいはずです。
于 2008-09-21T23:37:19.033 に答える
0
ハエを殺すためにバズーカを使用しないでください。SQLite のような単純なものを使用します。すべての現代言語に必要なすべてのツールがあり、次のことを実行できます。
"SELECT word FROM dict WHERE word LIKE "user_entry%"
電光石火の速さで、赤ちゃんでもできます。さらに、移植性があり、永続的であり、保守が非常に簡単です。
Pythonチュートリアル：
http://www.initd.org/pub/software/pysqlite/doc/usage-guide.html
于 2008-09-22T09:39:15.467 に答える
0
辞書が非常に大きい場合は、python テキスト インデックスを使用することをお勧めします (PyLucene - lucene の python 拡張機能を使用したことがないことに注意してください)。検索は効率的で、検索の「スコア」を返すこともできます。
また、ディクショナリが比較的静的な場合は、頻繁にインデックスを再作成するオーバーヘッドさえありません。
于 2008-09-22T02:05:02.517 に答える
0
線形スキャンは遅いですが、プレフィックス ツリーはおそらくやり過ぎです。単語を並べ替えてバイナリ検索を使用することは、迅速かつ簡単な妥協点です。
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']
于 2008-11-20T19:04:05.080 に答える