algorithm - 如何搜索以给定字母开头的单词

Question

我想在 Prolog 中实现一个搜索功能，当我输入一个字母时，它会显示建议的单词，从该字母动态开始。

作为起点，我试图找到一种方法来获取从给定字母开始的单词列表。但我找不到任何可以尝试的东西。

score 2 · Accepted Answer

这听起来像是一个有价值的项目，不仅适用于初学者。大多数复杂性都应该由用户交互来承担。您应该细分您的任务 - 首先：

单词表示
用户交互（什么媒体？）
- '下一个字符' 采集
- 列表显示
- 错误处理？

例如，使用基本的 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 手册。

score 0 · Accepted Answer

您需要的是一种称为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 事实将是更难的部分。

algorithm - 如何搜索以给定字母开头的单词

2 回答 2

Related

Reference