我正在阅读有关绳索的论文“绳索：字符串的替代方案”
[来自同一篇论文的图]
我想知道这是否是当今浏览器用于实现文本框的数据结构。我们是否为此使用绳索或其他一些数据结构？
除了文本框之外，还有其他地方使用绳索吗？
我问题的前一个标题不知何故也意味着我想知道字符串“记住”是如何发生的——当我输入时，我会得到建议。我现在已经改变了。
我想知道的是当我键入它时使用什么数据结构来存储字符串。它是像 char 数组这样简单的东西还是像绳子这样复杂的东西？
问问题
337 次
3 回答
1
很可能只使用底层操作系统/窗口系统提供的任何文本框。我猜至少在大多数情况下，这将是一个用于文本框的简单线性数组——大多数情况下很少会保存接近像绳子这样的东西真正有意义所需的数据量。
于 2010-08-24T02:57:01.120 回答
0
问题（在一个简单的情况下）是找到所有包含一些子字符串的字符串。由于它并不总是搜索常见的作品甚至字母，我的猜测是某种http://en.wikipedia.org/wiki/N-gram索引。例如，对于三元组：
- 对于每个要索引的字符串，找到 3 个字符（三元组）的所有（重叠）子序列。
- 对于每个子序列，存储它出现的所有字符串的列表。这是索引，它是来自 trigram -> 字符串列表的映射。
- 如果用户输入一个关键字，找到它的三元组，在索引中查找它们，并返回相应字符串列表的交集。
这是返回可能包含该单词的字符串的一种快速方法。为了更精确，可以将结果过滤到包含整个子字符串的结果。
浏览器可以通过多种方式增强这一点，例如，如果输入了多个单词，它们可以搜索每个单词并返回包含其中任何一个的 URL。
于 2010-08-24T03:03:48.667 回答
0
他们使用前缀匹配算法。Trie（及其高级版本）是实现最长前缀匹配的最佳方式。
注意：我假设您的意思是他们在您键入时如何“记住”文本。
如果您的意思是每个文本框如何包含您之前键入的内容的列表并在弹出窗口中显示它 - 每次您“提交”使用该文本时都会附加一个列表。
于 2010-08-24T04:14:32.063 回答