プログラミングについて質問です。


クロスワードクイズで二重四角の中の文字を並べ替えて言葉を作ってくださいというのがよくあります。

例えば「ずうぼるてるて」と文字列があったとして
コレを並べ替えて総当りで辞書とマッチングさせて
意味のある言葉かどうか判定したいと思います。

文字列の並び替えは大丈夫なのですが、辞書とマッチングさせる方法がよくわかりません。

フリーの言語で開発したいのでC言語かjavaで参考になるサンプルがあれば教えてください。

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2007/06/27 21:07:06
  • 終了:2007/07/04 21:10:03

回答(3件)

id:t_shiono No.1

t_shiono回答回数256ベストアンサー獲得回数222007/06/27 22:00:09

ポイント35pt

辞書は何を想定していますか?それによって回答は異なります。

例えば、何か辞書ファイルを持っているのであれば、その辞書ファイルの構造によってきますので、それを聞かないと答えられません。

また、オンライン辞書の検索を想定しているのであれば、

HTTPでの検索ページの取得し

(参考:http://x68000.q-e-d.net/~68user/net/java-http-url-connection-1.h...

正規表現でその言葉が見つかったかどうかを判定する

(参考:http://www.hellohiro.com/regex.htm

という感じでしょうか?

id:castiron No.2

castiron回答回数418ベストアンサー獲得回数302007/06/27 22:07:52

ポイント35pt

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

こっちはハッシュ法をつかっている。

「探索 アルゴリズム」で検索すれば似たようなのがいくらでも出てきます。

id:quintia No.3

quintia回答回数559ベストアンサー獲得回数682007/06/28 21:43:10

ポイント10pt

直接の回答じゃないですけど。


辞書にある言葉に対応した、"文字を辞書順に整列させた項目"を作った方がいいんじゃないですか? ("含まれているのが同じ文字なら同じパターンが生成される"ことが保証されるなら他の規則でもいいですけど)


かいとう,回答

かいとう,解答

かいとう,怪盗

とうかい,東海

とうかい,韜晦

とかい,都会

かいと,カイト


という正解を集めた辞書があるとして、


いうかと,かいとう,回答

いうかと,かいとう,解答

いうかと,かいとう,怪盗

いうかと,とうかい,東海

いうかと,とうかい,韜晦

いかと,とかい,都会

いかと,かいと,カイト


というように、先頭項目を追加します。

[か,い,と,う]から、い < う < か < と の性質を利用して、[い,う,か,と]を作るわけです。


「といかう」という答えがでてきたら、

[と,い,か,う]から[い,う,か,と]と変形(配列と見なすとソート)して、辞書の一番目の項目が「いうかと」なものを探します。

それでマッチしたものはどれも「正解」ですよね?

上の辞書でいえば、回答、解答、怪盗、東海、韜晦 が得られます。


ダミー

http://www.google.com/

コメントはまだありません

この質問への反応(ブックマークコメント)

トラックバック

  • [Program]辞書に登録された文字列と文字がシャッフルされている文字列の判定方法 d金魚による C/C++にてプログラミングする為のノウハウとアルゴリズムの公開とライブラリとアプリケーションの開発の過程を記す dKingyo SDK 日記 2007-06-29 02:25:08
    Powered by dKingyo ソフトウェア開発技術者 | Rails | Python | Game Programming Gems | Perl http://q.hatena.ne.jp/1182946023 より・・・。 興味深い。 と言う事でちょっと考える。私ならば・・・ 辞書ファイルを用
「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません