问题标签 [string-search]

我有一个字符串数据库（任意长度），其中包含超过一百万个项目（可能更多）。

我需要将用户提供的字符串与整个数据库进行比较，如果存在则检索相同的字符串，否则返回最接近的模糊匹配（60% 相似性或更好）。理想情况下，搜索时间应低于一秒。

我的想法是在根据长度缩小数据库中的候选者之后，使用编辑距离将每个数据库字符串与搜索字符串进行比较。

但是，由于我需要经常执行此操作，我正在考虑构建数据库字符串的索引以保存在内存中并查询索引，而不是直接查询数据库。

关于如何以不同方式解决此问题或如何构建内存索引的任何想法？

在编写 C++ 时，我使用 Visual Studio 的 Vim 和 Vim 插件。通常，我发现自己想在函数中搜索字符串，例如每次调用object->public_member.memberfunc().

我知道 Vim 提供了一种方便的方法来搜索单个单词，通过按*and #，它还可以使用无处不在的斜杠/命令搜索键入的字符串。当尝试搜索像上面这样的较长字符串的所有实例时，重新键入 after 需要一段时间/。

有没有办法搜索选择？比如用 高亮v，然后用 复制y，有没有办法在后面粘贴/？有没有更简单的捷径？

如何搜索 in table_a table_b table_c，其中包含随机数列的字符串？

我知道这不是正确的 sql，但它会是这样的：

提前为 SO 社区提供 Ty

为了使 Boyer-Moore 算法成为最坏情况线性，失配表的计算必须是 O(m)。然而，一个简单的实现将遍历所有后缀 O(m) 以及该后缀中的所有位置可以检查是否相等......这是 O(m ³ )！

下面是建表算法的简单实现。所以这个问题变成了：我怎样才能把这个算法的运行时间提高到 O(m)？

为了让思想休息，这不是家庭作业。当有人发布改进想法时，我会添加修订。

我可能会错误地问这个问题，但我想做的是以下内容：

给定一个可能有 100 多行的大字符串，匹配并准确替换一个单词，并确保它不会替换和匹配任何其他字符串的任何部分。

例如 ：

输出

我尝试过使用单词边界使用正则表达式，尽管这'whichwhillerrorMacO'在最后一行出现。

我也尝试使用StringTokenizer类和各种分隔符来尝试替换单词，但是我尝试替换的一些单词包含这些分隔符。

有没有可以解决这个问题的正则表达式？

有可用于普通字符串搜索算法的 Python 代码，例如 Boyer-Moore。我希望在汉字上使用它，但似乎相同的实现不起作用。为了使算法适用于汉字，我该怎么做？我指的是这个：

http://en.literateprograms.org/Boyer-Moore_string_search_algorithm_(Python)#References

我有一堆二进制文件，每个文件都在文件末尾附近包含一个嵌入的字符串，但在不同的位置（每个文件中只出现一次）。我需要提取从字符串位置开始直到文件末尾的文件部分并将其转储到一个新文件中。

例如。如果文件的内容是“AWREDEDEDEXXXERESSDSDS”并且感兴趣的字符串是“XXX”，那么我需要的文件部分是“XXXERESSDSDS”。

在 bash 中执行此操作的最简单方法是什么？

对于两种字符串搜索算法：KMP 和后缀树，哪种情况下首选？举一些实际的例子。

我很好奇在一段文本中计算字符串出现次数的最有效算法（或常用算法）是什么。

根据我的阅读，Boyer–Moore 字符串搜索算法是字符串搜索的标准，但我不确定以有效方式计算出现次数是否与搜索字符串相同。

在 Python 中，这就是我想要的：

编辑：似乎 pythonstr.count就是这样一种方法；但是，我无法找到它使用的算法。

我正在构建一个从 6 个 csv 样式文件和两个布局不佳的 .txt 报告中提取数据并构建输出 CSV 的过程，并且我完全意识到在所有这些空白中搜索数千次会产生一些开销，但我从没想过转换大约 50,000 条记录需要 12 个小时。

我的手动匹配代码的摘录（我知道我使用这样的标记列表很糟糕，但这是我能想到的最好的事情）：

基本上想知道我将如何进行有效的字符串搜索（Boyer-Moore 或类似）。我的 Scannerid正在扫描一个java.util.String，认为将其缓冲到内存会减少 I/O，因为这里的搜索在一个相对较小的文件上执行了数千次。与扫描 BufferedReader(FileReader(File)) 相比，性能提升可能不到 1%，这个过程看起来仍然需要很长时间。

我还跟踪了执行情况，我的整体转换过程的缓慢肯定介于查找方法的第一个和最后一个之间。事实上，以至于我运行了一个快捷过程来计算 .csv 样式文件中各种标识符的出现次数（我使用 2 种查找方法，这只是其中一种），并且该过程完成了大约 4 个不同的索引在不到一分钟的时间内识别出 50,000 条记录的标识符。与12小时相比，那是瞬间的。

一些注释（2010 年 6 月 6 日更新）：

1. 我仍然需要 tokensBefore 的模式匹配行为。
2. 我需要的所有 ID 号不一定从一行中的固定位置开始，但可以保证 ID 标记之后是相应对象的名称。
3. 理想情况下，我希望返回一个字符串，而不是结果的起始位置作为 int 或其他东西。

任何可以帮助我的事情，即使每次搜索可以节省 1 毫秒，也会有所帮助，因此所有输入都将受到赞赏。谢谢！

使用场景 1：我在文件 A 中有一个对象列表，在旧式系统中，这些对象的 ID 号不在文件 A 中。但是，它可能在另一个 csv 样式文件（文件 B）中，或者可能仍然在一个 .txt 报告（文件 C）中，每个报告还包含一堆其他在这里没用的信息，因此需要在文件 B 中搜索对象的全名（1 个标记，因为它会驻留在第二列中任何给定行），然后第一列应该是 ID 号。如果这不起作用，那么我们必须通过空格将搜索标记拆分为单独的标记，然后再在文件 C 中搜索这些标记。

通用代码：

objectName 标记都是大写单词，其中可能包含连字符或撇号，由空格（人名）分隔。

根据 aioobe 的回答，我已经为我的常量搜索令牌预编译了正则表达式，在这种情况下只是\r\n. 在我编译的另一个进程中，注意到的加速大约是 20 倍[0-9]{1,3}\\.[0-9]%|\r\n|0|[A-Z'-]+，尽管在上面的代码中没有注意到\r\n. 沿着这些思路工作，我想知道：

\r\n[^ ]如果唯一可用的匹配项无论如何都在以非空格字符开头的行上，对我来说匹配会更好吗？它可能会减少 _match 执行的次数。

另一种可能的优化是：连接所有标记之后，并(.*)预先放置一个。它将减少大约 2/3 编译的正则表达式（无论如何都是文字）的数量，并且还希望允许我从该分组中提取文本，而不是从每一行中保留一个“潜在标记”上面有身份证。这也值得吗？

如果我可以在调用 findWithinHorizo​​n 后让 java.util.Scanner 返回当前令牌之前的令牌，则可以解决上述情况。