クロスワードクイズで二重四角の中の文字を並べ替えて言葉を作ってくださいというのがよくあります。
例えば「ずうぼるてるて」と文字列があったとして
コレを並べ替えて総当りで辞書とマッチングさせて
意味のある言葉かどうか判定したいと思います。
文字列の並び替えは大丈夫なのですが、辞書とマッチングさせる方法がよくわかりません。
フリーの言語で開発したいのでC言語かjavaで参考になるサンプルがあれば教えてください。
辞書は何を想定していますか?それによって回答は異なります。
例えば、何か辞書ファイルを持っているのであれば、その辞書ファイルの構造によってきますので、それを聞かないと答えられません。
また、オンライン辞書の検索を想定しているのであれば、
HTTPでの検索ページの取得し
(参考:http://x68000.q-e-d.net/~68user/net/java-http-url-connection-1.h...)
正規表現でその言葉が見つかったかどうかを判定する
(参考:http://www.hellohiro.com/regex.htm)
という感じでしょうか?
http://www1.cts.ne.jp/~clab/hsample/File/File10/File10.html
バイナリサーチとかを使ってやれば良いかな?
この予約後の配列をファイルから読み込むようにすれば良いんじゃないかな?
http://www.na.cse.nagoya-u.ac.jp/~reiji/lect/alg99/sec6-4.html
こっちはハッシュ法をつかっている。
「探索 アルゴリズム」で検索すれば似たようなのがいくらでも出てきます。
直接の回答じゃないですけど。
辞書にある言葉に対応した、"文字を辞書順に整列させた項目"を作った方がいいんじゃないですか? ("含まれているのが同じ文字なら同じパターンが生成される"ことが保証されるなら他の規則でもいいですけど)
かいとう,回答
かいとう,解答
かいとう,怪盗
とうかい,東海
とうかい,韜晦
とかい,都会
かいと,カイト
という正解を集めた辞書があるとして、
いうかと,かいとう,回答
いうかと,かいとう,解答
いうかと,かいとう,怪盗
いうかと,とうかい,東海
いうかと,とうかい,韜晦
いかと,とかい,都会
いかと,かいと,カイト
というように、先頭項目を追加します。
[か,い,と,う]から、い < う < か < と の性質を利用して、[い,う,か,と]を作るわけです。
「といかう」という答えがでてきたら、
[と,い,か,う]から[い,う,か,と]と変形(配列と見なすとソート)して、辞書の一番目の項目が「いうかと」なものを探します。
それでマッチしたものはどれも「正解」ですよね?
上の辞書でいえば、回答、解答、怪盗、東海、韜晦 が得られます。
ダミー
コメント(0件)