我想在 Prolog 中实现一个搜索功能,当我输入一个字母时,它会显示建议的单词,从该字母动态开始。
作为起点,我试图找到一种方法来获取从给定字母开始的单词列表。但我找不到任何可以尝试的东西。
这听起来像是一个有价值的项目,不仅适用于初学者。大多数复杂性都应该由用户交互来承担。您应该细分您的任务 - 首先:
例如,使用基本的 Prolog IO 和 vanilla words 的数据库:
word("prolog").
word("programming").
word("algorithm").
word("word").
user_interface(SelectedSoFar, SelectedWord) :-
% get a sorted set of matched words rest
( setof(Rest, Word^(word(Word), append(SelectedSoFar, Rest, Word)), Matched)
-> ( Matched = [Choosed] % only 1 choice available ?
-> append(SelectedSoFar, Choosed, SelectedWord) % terminate
; % display list, get next char, recurse
forall(member(Rest, Matched), format('~s^~s~n', [SelectedSoFar, Rest])),
get(C),
append(SelectedSoFar, [C], ExtendedSel),
user_interface(ExtendedSel, SelectedWord)
)
; writeln('no match, retry'),
append(WithoutLast, [_], SelectedSoFar), % discard last - BUG: swapped arguments
user_interface(WithoutLast, SelectedWord)
).
示例交互:
?- user_interface("",W).
^algorithm
^programming
^prolog
^word
|: w
W = "word".
?- user_interface("",W).
^algorithm
^programming
^prolog
^word
|: p
p^rogramming
p^rolog
|: r
pr^ogramming
pr^olog
|: o
pro^gramming
pro^log
|: g
W = "programming".
编辑:我已经更正了一个错误,请参阅最后的评论 % discard ....
你看到的地方(例如)
|: w
我输入了一个字符和一个“回车”。这是一个非常基本的界面......您至少应该接受一个字符串,而不是单个字符。见 Prolog 手册。
您需要的是一种称为trie的数据结构。您可以在以下位置阅读有关它们的信息
任何优秀的算法书籍,例如 Robert Sedgewick 的算法,都会进行一些详细的尝试。这是Jon Bentley 和 Robert Sedgewick 撰写的一篇可能有用的论文,Fast Algorithms for Sorting and Searching Strings 。
一点google-fu建议YAP Prolog有一个内置的 trie 实现,根据它的手册。这是关于 prolog 中的 trie 实现的讨论:http ://computer-programming-forum.com/55-prolog/59e7d719f1e1d18f.htm
我怀疑您会发现在 prolog 中表示 trie 相对简单。这项工作将是从字典中填充树。编写一个程序来阅读您的字典并生成 trie 作为 prolog 事实将是更难的部分。