何万語の中から該当する語を瞬時に検索する方法

Question

この質問はこのサイトの趣旨に沿っていなければ申し訳ありません
今辞書アプリなるものを初めて作っていまして、この疑問にあたりました

辞書アプリの検索機能のプログラムについての質問です
辞書アプリなどの大量の情報が必要なアプリで、任意の単語を検索機能で検索すると一瞬で該当するものが表示されます。そんな一瞬でヒットできるものなんでしょうか
例えば、英和辞書なら見出し語が9万語以上あるのにそんな一瞬で探し出せるのでしょうか?
というのも素人考えで、検索機能を考えたんですけど
見出し語がリストに格納してあって、検索にかけられた単語と1個1個一致するのを探していく
見出し語リストは、頭文字がどのアルファベットから始まるかでaからzでふり分けられていて、で、検索にかけられた単語の頭文字と一致するところをまた1個1個一致するまで検索していく
これで検索する量が多くとも6分の1ほどの1万ちょっとには抑えられます(sから始まる単語が全体の1/6くらいある)

//見出し語のリスト　(語順適当です)
//List = [[apple,...], [bat,...],[candy,..],. .... ,[zoo,...]]

みたいなイメージです
1万個のデータのどれと一致するか判断するのに1,2秒じゃ足りないと思います
何か根本的に違う検索の仕方をしているんでしょうか

もうひとつ質問があってデータについてです
単語の説明文などはtxtでまとめて保存すべきかとかプログラムにstringで直に書き込んでいくべきかなどそういったことは、どういううキーワードで調べたらいいですか

回答よろしくお願いします

Comments

[jimbe]

データが有るのでしたら、何事も経験と思って考えた方法でやってみては如何でしょうか。

[hoshi-takanori]

とりあえずアルゴリズムやデータ構造を学ぶと良いかも。二分探索とかハッシュ表とかツリー構造とか…。

Answer 1

m.ts10806さんが書かれていますが、辞書は辞書データと別に大量のインデックスを持っています。

電子辞書データの規格であるEPWINGについて調べれば、そのデータ構造はわかります。
更に極めよ「EPWING/PDIC辞書」あたりを見れば、辞書の作成方法も書いてありますので、作ってみれば元データよりも大きなデータが作られていることは良くわかります。

EPWING辞書の検索ソフトもいろいろありますが、GitHub FooSoft/yomichanのようにソースが公開されているものもありますので、読んでみると良いかもしれません。

自作にこだわらなれば、EPWING辞書の適当なインタフェースの検索ライブラリも見つかるはずですのでそれを使うという方法も検討されてはいかがでしょうか。

Answer 2

見出し語

こちら本件を解決するためのキーワードになり得ます。
既に出ているように一般的には大量データの操作はデータベースを利用します。
データにキーやインデックスといった設定を適切にすることで高速に目的のデータまで辿り着くことができるわけです。
※部分一致や文字列検索だと若干パフォーマンスは落ちますがそれでも全件ループするよりは圧倒的に速い

Answer 3

実装方法は色々ありますが、簡単にできる例を一つ言えば、a フォルダの中の p フォルダの中の p フォルダの中の l フォルダの中の e フォルダがあれば apple が辞書にあり、その中に ja.txt があればそこにはリンゴと書かれているとすれば良いのではないでしょうか。

より最適化するには「探索木」を調べてみてください。

Answer 4

普通の紙の辞書を考えてみてください。
調べようとした単語を適当に開いて、そのページ載ってなくても
順番にならんでいてるので開いたページの前にあるか、後ろにあるか、わかりますよね？
開いたページから前にあるか後ろにあるかわかっているので、無い方を調べませんよね？
１件１件全件比較しなくてもいいことがわかりますよね？

Answer 5

まあフツーはデータベース(DBMS)に丸投げするのかな。
それができないなら上記相当のことを自分で実装することに。
たぶん(情報があるなら)CODASYL系のが参考にかると思います。

メモリを潤沢に使っていいなら話は早いですけど
そういうのはあんまり無いでしょうからね～

ちなみに、データとコードは分けとく方が主流でしょう。
なんか特別な理由があれば別ですけどね。

Answer 6

4億行を超えるテキストから前方一致で2万件取り出すシェルスクリプトを書いたことがありますが、grepだと3年くらいかかりそうだったので、lookというコマンドを使いました。こいつはまず探査対象がソート済みであることが条件で「2分探査法」という検索方法をとります、真ん中で割ってどっちにいるかを繰り返す検索方法です。爆速でした。

Answer 7

検索そのものは皆さん書かれてますので、もう一つの側面を。
辞書の様に 見出し語 だけで検索しますか？
それとも「辞書アプリの検索機能のプログラムについての質問です」をhitさせるのに

1. 辞書、アプリ、検索、機能、プログラム、質問 のどれでもhitさせたいです
2. 辞典、事典、字典、じしょ、じてん としてもhitさせたいですか？

1 でしたら、文章を細切れにする技術が必要です
2 は類似語を集めた辞書が必要です。