问题标签 [string-search]

我正在寻找一种在文本中查找某些特定模式的方法。例如，如果我想从如下格式的文本中查找所有引用：

• Baron, Naomi (2000) 字母到电子邮件：书面英语是如何演变的以及它的发展方向，劳特利奇：伦敦和纽约。

所以任何类似的东西都会从输入文本中返回。有什么算法可以很好的解决这个问题。到目前为止，我发现的只是在文本中搜索相似字符串的算法。

我正在考虑使用正则表达式，但我不知道这是否是最好的方法，因为我需要一些东西来计算一些相似性指数，然后返回得分最高的命中。

我需要实现一个字符串搜索算法，该算法在位文本中找到位模式（匹配可能不是字节/字对齐的）。首先，我实现了 Boyer-Moore 算法，但比较单个位对我来说太慢了。因此，我尝试实现一个基于阻塞的版本，该版本将比较本文中描述的整个字节/单词，但它变得复杂且难以管理（部分原因是我不完全理解我在做什么。）

有没有人很好地实现了这种算法？

我的具体用例是将模式长度N >= 32、文本窗口2N和位打包到ints 中。在N这种情况下也是 char size 的倍数N % 8 == 0。我预处理一次并在更改文本时多次使用，例如 Boyer-Moore。第一场比赛就是我所需要的。性能是关键。

编辑：在成功实现 Blocked Boyer-Moore 算法后，我发现没有任何改进（我的一点一点的版本更快！）这可能是我自己的错误，因为我一直在绞尽脑汁优化它没有多行评论就没有意义，但它仍然很慢。在这里。

给定一组 100 万（非常大）的编号。URL 的。从列表中找到“第一个”“唯一”URL。

我的方法：使用完美的散列函数构建散列，这会有所帮助。但是我的问题是散列大数据是不可能的，那么我该如何解决这个问题。

有什么方法可以就地做吗？请帮忙。提前致谢。

我有一个看起来像这样的人类字典文件eng.dic（该列表中有近十亿个单词的图像）。而且我必须经常运行不同的单词查询。

我有一个字符串让我们说“foo-bar”，是否有更好（更有效的方法）搜索该文件以查看它是否存在，如果它返回存在，如果它不存在，附加字典文件

python中是否有任何内置的搜索功能？或任何我可以导入以运行此类搜索而无需太多开销的库？

Knuth-Morris-Pratt搜索算法和Boyer-Moore搜索算法之间的主要区别是什么？

我知道KMP在 X 中搜索 Y，试图在 Y 中定义一个模式，并将该模式​​保存在一个向量中。我也知道BM更适合小词，比如 DNA (ACTG)。

它们在工作方式上的主要区别是什么？哪个更快？哪一个对计算机不那么贪婪？在哪些情况下？

面试中有一个问题问我，但我无法回答。

问题是：

你得到一个有向图，其中每个节点都是一个字符，你还得到一个字符串数组。任务是通过在图中搜索来计算数组中每个字符串的频率。

我的做法：我用了trie、Suffix tree，但面试官并不完全满意。你能给我一个给定问题的算法吗？

我一直试图理解Boyer–Moore 字符串搜索算法中的移位规则，但还没有理解它们。我在维基百科上读到这里，但这太复杂了！

如果有人以简单的方式列出规则，那将有很大帮助。

我必须从大型 PDF 文档中构建某种“字符串目录”，以便更快地搜索字符串/子字符串。

该机制应该像这样工作：PDF 扫描仪扫描 PDF 文档中的字符串，并在我的目录中调用回调方法来索引该字符串。

现在，应该使用什么技术来构建这样的目录？我听说过： - 后缀树 - 广义后缀树 - 后缀数组

我主要倾向于广义后缀树。那我是对还是错？我猜“普通”后缀树只适用于索引单个字符串。

但是后缀数组呢？那里有通用的后缀数组吗？

我在 C/C++ 中发现了很多用于从字符串构建后缀树的代码，但没有用于构建通用后缀树的代码！

有谁知道我如何使 IN 子句以区分大小写的方式运行？我已经看到 COLLATE 可以与 LIKE 一起用于字符串搜索，但我不知道它是否或如何与 IN 一起使用。例如，我想做类似的事情

我希望它返回主题为“食物”的页面，但不返回主题为“食物”的页面，而这正是当前在此查询中发生的情况。谢谢。

我编写了一个程序来搜索段落中的给定短语，并在该段落中用花括号将短语括起来。我已经使用 BoyerMoore 的算法进行搜索。同时我还需要提高程序的性能。虽然我得到了所需的输出，但性能是灾难性的。

这是代码：

我可以实施或做些什么来提高我的程序的性能？我应该切换到另一种字符串搜索算法吗？

如果有人可以帮我解决这个问题？