问题标签 [string-matching]

我正在尝试建模一个语音识别器，该识别器必须从每个单词之间没有间隙的长音素流中分离出单词实例（音素串）。电话流的识别可能很差，有字母替换/插入/删除，所以我将不得不进行近似的字符串匹配。

但是，我希望匹配以语音为动机，例如“m”和“n”在语音上相似，因此与“m”和“k”相比，“m”对“n”的替换成本应该很小”。因此，如果我正在搜索 [mein] “main”，它将匹配字母序列 [meim] “maim” 与成本 0.1，而它将与字母序列 [meik] “make” 匹配，例如，成本 0.7。同样，插入或删除每个字母的成本也不同。我可以提供一个混淆矩阵，对于每个字母对 (x,y)，给出用 y 代替 x 的成本，其中 x 和 y 是任何字母或空字符串。

我知道有一些工具可以进行近似匹配，例如agrep，但据我所知，它们不会将混淆矩阵作为输入。也就是说，任何插入/替换/删除的成本 = 1。我的问题是，是否有任何可用的开源工具可以与混淆矩阵进行近似匹配，如果没有，我可以实现什么好的算法要做到这一点？

编辑：为了清楚起见，我试图从较长的字符串（例如 [aiammeinlimeiking...]）中分离出诸如 [mein] 之类的单词的近似实例。理想情况下，算法/工具应该报告成本为 0.0（精确匹配）的 [mein]、成本为 0.7（接近匹配）的 [meik] 等所有成本低于给定阈值的近似字符串匹配的实例。

我有一个巨大的文本文件的字符串缓冲区。我必须在字符串缓冲区中搜索给定的单词/短语。什么是有效的方法？

我尝试使用 re 模块匹配。但是因为我有一个巨大的文本语料库，我必须搜索。这需要大量时间。

给定一个单词和短语字典。

我遍历每个文件，将其读入 string ，搜索字典中的所有单词和短语，如果找到键，则增加字典中的计数。

我们认为的一个小优化是将具有最大单词数的短语/单词字典排序到最低。然后从字符串缓冲区比较每个单词的起始位置并比较单词列表。如果找到一个短语，我们不会搜索其他短语（因为它匹配最长的短语，这就是我们想要的）

有人可以建议如何在字符串缓冲区中逐字进行。（逐字迭代字符串缓冲区）？

另外，还有其他可以做的优化吗？

Lucene 模糊匹配使用基本的editDistance 算法来实现模糊匹配。Lucene 是否还有其他使用其他相似性度量的模糊匹配实现？他们也应该识别同音字。还请比较 lucene 的各种模糊匹配方法。

我试图在一组字段中找到几乎重复的值，以便管理员清理它们。

我符合两个条件

1. 一个字符串完全包含在另一个字符串中，并且至少是其长度的 1/4
2. 字符串的编辑距离小于两个字符串总长度的 5%

伪 PHP 代码：

我试图尽可能减少对相对昂贵的函数的调用stripos，levenshtein这大大减少了执行时间。然而，作为一个 O(n^2) 操作，这并不能扩展到更大的值集，而且似乎大量的处理时间都花在了简单地遍历数组上。

正在操作的几组值的一些属性

我可以做些什么来减少检查标准的时间，更重要的是，我有什么方法可以减少所需的标准检查次数（例如，通过预处理输入值），因为有这样的选择性低？

编辑：实施的解决方案

我想确定一个字符串是否是一个月的名称，并且我想相对快速地完成它。目前卡在我大脑中的功能是这样的：

但是，我将处理大量文本，一次将一个字符串传递给这个函数，而且大多数时候我会遇到最坏的情况，即遍历整个循环并返回 false。

我看到另一个问题，它谈到了一个正则表达式来匹配一个月份名称和一个可以适应这种情况的年份。正则表达式会更快吗？有没有其他可能更快的解决方案？

有什么方法可以让 JPQL 匹配相似的字符串？

类似的意思是：

• 包含：在匹配实体的字符串中找到搜索字符串
• 不区分大小写
• 小错误：例如“arow”匹配“arrow”

我怀疑前两个会很容易，但是，我会感谢最后一个的帮助

谢谢

我需要比较 2 组音乐作品（即以 MIDI 格式录制的演奏 - 提取并保存在数据库表中的音符细节，与以 XML 格式录制的乐谱）。在评估演奏乐谱时（即音符细节 - 音高、持续时间、节奏），需要进行音符对齐 - 以识别参考（乐谱）音符中遗漏/额外/不正确/交换的音符。

我大约有 1800-2500 个音符（甚至可以更多 - 与复音，现在我正在为单音做）。那么我是否必须将所有这些都放入一个数组中？会是内存过载还是堆栈溢出？

有 KMP、Boyce-Moore 等字符串匹配算法。但是音符对齐也可以通过动态编程来完成。我如何使用动态编程来解决这个问题？有哪些可用的算法？是关于近似字符串匹配吗？

哪种方法效率高？像 Boyce-Moore 这样的字符串匹配算法，还是动态编程？我如何评估哪个更有效？

非常感谢任何见解或建议在此先感谢

我需要在乐曲（例如存储在表格中的音符音高[字符串值]）中针对参考找到 1.mismatch（错误演奏的音符）、2.insertion（附加演奏）和 3.deletion（遗漏的音符）音乐片。

这可以通过精确字符串匹配算法或动态编程/近似字符串匹配算法来实现。但是我意识到，由于识别不匹配、插入、删除注释，近似字符串匹配更适合我的问题。或 Boyer-moore 的扩展版本以支持大约。字符串匹配。

是否有示例 java 代码的链接我可以尝试近似字符串匹配？我找到了复杂的解释和方程式——但我希望我能用一些示例代码和简单的解释做得很好。或者我可以在 boyer-moore 上找到任何示例 java 代码扩展约。字符串匹配？我理解 boyer-moore 的概念，但是在调整它以支持大约。字符串匹配（即支持不匹配、插入、删除）。

还有什么是最有效的。字符串匹配算法（如精确字符串匹配算法中的 boyer-moore）？

非常感谢任何见解/建议。提前谢谢了

这是“算法设计与分析导论”中的练习。这是一个字符串匹配问题。假设我有字符串 ABCD，并且有一个模式 XY。并想看看字符串是否包含模式。

我们只是假设在这里使用蛮力，所以从左到右的比较是比较 A 和 X，接下来是比较 B 和 X，等等。而从右到左的比较是比较 B 和 Y，接下来是比较 C与 B. 提示说从右到左比较确实有优势，但我不明白为什么。

任何提示表示赞赏！

我想要一个可用于查找以下行的正则表达式：

并用这些行替换它们：

谢谢你 。