问题标签 [string-algorithm]

关于 SO 的另一个问题提出了一些语言的工具来散列字符串，以便在表中快速查找。这方面的两个示例是 .NET 中的字典<> 和 Python 中的 {} 存储结构。其他语言当然支持这种机制。C++ 有它的映射，LISP 有一个等价物，就像大多数其他现代语言一样。

在对字符串的哈希算法可以在恒定时间内进行的问题的答案中提出了争议，一位拥有 25 年编程经验的 SO 成员声称任何东西都可以在恒定时间内进行哈希处理。我个人的观点是，这不是真的，除非您的特定应用程序在字符串长度上设置了边界。这意味着某个常数 K 将决定字符串的最大长度。

我熟悉 Rabin-Karp 算法，它使用散列函数进行操作，但该算法并没有规定要使用特定的散列函数，作者建议的是 O(m)，其中 m 是哈希字符串。

我看到其他一些页面，例如这个（http://www.cse.yorku.ca/~oz/hash.html）显示一些哈希算法，但似乎每个页面都在字符串的整个长度上进行迭代达到它的价值。

从我对该主题的相对有限的阅读来看，似乎大多数字符串类型的关联数组实际上是使用散列函数创建的，该函数在引擎盖下使用某种树进行操作。这可能是指向键/值对中值元素位置的 AVL 树或红/黑树。

即使使用这种树结构，如果我们要保持在 theta(log(n)) 的顺序上，其中 n 是树中元素的数量，我们需要有一个恒定时间的哈希算法。否则，我们有迭代字符串的附加惩罚。即使对于包含许多字符串的索引，theta(m) 会被 theta(log(n)) 黯然失色，但如果我们处于这样一个域中，我们搜索的文本将非常大，我们也不能忽略它。

我知道后缀树/数组和 Aho-Corasick 可以将搜索降低到 theta(m) 以获得更大的内存开销，但我要特别问的是，对于任意长度的字符串是否存在恒定时间哈希方法由其他 SO 成员声明。

谢谢。

有很多关于字符串算法的帖子：

• 查找具有相似文本的文章的算法，
• 类似的字符串算法，
• 高效的字符串匹配算法

但是，没有提到一般文献。

谁能推荐一本可以彻底探索各种字符串算法的书？特别感兴趣的主题是近似字符串匹配[例如谷歌提供的更正搜索字符串变体:)]。

非常感谢您的建议。

如何在 O(n) 中找到字符串的最长回文前缀？

您如何在长长的字符流中找到正确的单词？

输入 ：

谷歌的输出：

（考虑到他们产生输出的时间，这已经足够接近了）

你觉得谷歌是怎么做到的？您将如何提高准确性？

我在我的 PHP 项目中有这个问题要解决，其中一些关键字（从几百到几千，长度可能会有所不同）需要在大约 100-300 个字符长的字符串中进行搜索，有时长度较短，为 30-50 个字符。我可以预处理关键字以重用于搜索字符串的新实例。我是 PHP 的新手，在 PHP 库中没有找到这样做的方法。经过一番搜索，我在 Aho Corasick 算法中找到了一些不错的候选者，然后是 Sun Wu 和 Udi Manber 的改进，它似乎也被称为 agrep（或者是 agrep 的一部分）：http://webglimpse。网/pubs/TR94-17.pdf

还有 Rabin Karp、Suffix Trees 等，但它们看起来不太适合，因为第一个是固定长度的关键字，而后者看起来很通用，需要做很多工作。

谁能让我知道我自己在 php 中实现 Agrep/Sun Wu-Manber 是解决这个问题的好方法吗？还有别的反馈吗？

编辑：正如我在下面的评论中提到的，有数百个或更多不同的搜索关键字，所以正则表达式无济于事。所以这种反应是没有帮助的。

我有一个包含 VARCHAR 类型列的表。我想根据用户输入查询在列内搜索字符串。我想实现近似搜索。我的表包含许多记录。我认为有一些方法可以实现搜索。

1. 在 C# 中加载所有记录并对其应用搜索算法。（但它会消耗太多的内存。）

2. 单独或以某些预定义的批量大小获取记录并对其应用搜索算法。（但它会快速建立数据库连接，这可能会降低性能。）

我确信，将会有一些其他的机制来实现这个功能或一些技术来存储数据，以便我可以更快地搜索它。

任何人都可以给我任何更好的想法来实现这个吗？

我需要在一个 c 字符串数组中搜索一个子字符串。

我创造了我认为会给我答案的东西，但它只是在语法上正确但在语义上是错误的，但我不确定我哪里出错了。

对此还有一个子问题。在向您展示我尝试过的示例后，我会问这个问题。

ir.first == ir.last

迭代器的结果表明我没有正确写这个。

我不确定第一个参数实际上const char [8]是否会产生不利影响。

我的主要问题是我应该如何纠正它，补充问题是如何从 constCharRange 或任何此类 typedef 中提取 find_first 所需的类型。

编辑：

我看到我错误地使用了 end 。然后，我设法获得了稍微不同的示例来工作，但是它们与我实际必须使用的定义不兼容（我可以添加到代码中，但不能更改现有定义）。

另一个测试

这是我能得到的最接近的值，但我似乎无法正确获取返回类型规范

在 PHP中是否有Aho–Corasick的工作实现？Wikipedia 文章中提到的PHP 中有一个Aho-Corasick 字符串匹配：

但是我很难使用它。它适用于一个婴儿示例，但如果我尝试加载数千个关键字，那么脚本会超过 30 秒的加载限制。

对于其他脚本语言，有很好的实现，例如http://metacpan.org/pod/Text::Scan for Perl 和http://pypi.python.org/pypi/ahocorasick/0.9 for Python。为什么不用于 PHP？

我正在构建一个数据结构来帮助索引总长度为 n 的 S 个文档的集合，以便它支持以下查询：给定两个单词 P1 和 P2，计算包含 P1 但不包含 P2 的所有文档。我希望答案是完整的（不要错过结果）。

我已经建立了一个通用的后缀树并选择每个 sqrt(n)-th 叶及其祖先（并删除每个单子节点）。对于每个内部节点 v，我预先计算针对节点 u 的查询的答案。

但是有了这个，如果查询包含出现在节点 v 和 u 中的树中的单词，我可以在 O(1) 中得到答案，但是当单词不在我们选择的节点之一时我该怎么办？

我可以通过使用预处理保持 O(n ² ) 数据结构并为 O(1) 时间检索准备好所有可能的答案来轻松做到这一点，但目标是在 O(n) 空间中构建此数据结构和使查询尽可能高效。

我正在尝试在 InterviewStreet 上解决这个挑战：https ://www.interviewstreet.com/challenges/dashboard/#problem/4edb8abd7cacd

我已经有了一个可行的算法，但我会提高它的性能。你有什么建议吗？

谢谢，格雷格