algorithm - 指定した文字で始まる単語を検索する方法

Question

Prolog に検索機能を実装したいと考えています。文字を入力すると、その文字から動的に始まる単語の候補が表示されます。

出発点として、指定された文字から始まる単語のリストを取得する方法を見つけようとしました。しかし、試してみるものが見つかりませんでした。

Answer 1

必要なのは、trieと呼ばれるデータ構造です。あなたはそれらについて読むことができます

• http://www.sarathlakshman.com/2011/03/03/implementing-autocomplete-with-trie-data-structure/
• http://en.wikipedia.org/wiki/Trie
• http://www.cs.bu.edu/teaching/c/tree/trie/

Robert Sedgewick のAlgorithmsなどの優れたアルゴリズムの本は、ある程度詳細に試行されます。Jon Bentley と Robert Sedgewick による、役に立つかもしれない論文Fast Algorithms for Sorting and Searching Stringsがあります。

ちょっとしたgoogle-fuは、マニュアルに従って、YAP Prologに組み込みの trie 実装があることを示唆しています。プロローグでのトライの実装に関する議論は次のとおりです。

プロローグでトライを表現するのは比較的簡単であることがわかると思います。ディクショナリからツリーを生成する作業が行われます。辞書を読み込んでプロローグの事実としてトライを生成するプログラムを書くのは難しい部分です。