问题标签 [string-matching]

我正在使用 perl 脚本读取文件。该文件由具有不同字符的字符串组成，我应该识别包含字符“X”的字符串。我想知道我应该如何（1）打印这个字符串（包含'X'）以及（2）把这个字符串写入另一个文件（3）计算整个文件中'X'字符的数量。下面的脚本再次打印整个文件。有什么建议么？

我正在努力完成以下工作。假设我们有一个包含这些字段（ID、内容）的表

1 | 苹果

2 | 菠萝

3 | 应用

4 | 国家

现在，我正在寻找一个可以告诉我所有可能的常见匹配项的函数。例如，如果参数为“3”，则该函数将返回出现在多于一条记录中的 3 个字符中的所有可能字符串。

在这种情况下，我得到 "app","ppl","ple","ati","tio","ion"

如果参数是“4”，我得到：“appl”，“pple”，“atio”，“tion”

如果参数是“5”，我得到：“apple”，“ation”

如果参数是“6”，则返回 nohting。

直到现在，我还没有找到实现这一点的功能。

谢谢！

一些额外的信息：我在一个带有 MySQL 数据库的 PHP 脚本中使用它。我真的只想给出字符数量作为参数，当然还有要搜索的表格。

我有各种长度的字符串，其中充满了 Base64 字符。实际上，它们是音频识别数据，因歌曲而异。

为了轻松比较这些字符串的各个部分，我将它们分成 16 个字符的子字符串。（大约是一首歌的 1 秒）但在某些情况下，我无法直接比较这些。我应该测量它们。

例如与 ' hellohellohelloo' 和 ' hallohellohelloo' 的比较应该得到更接近的值然后 ' hellohellohelloo' 和 ' herehellohelloo' 比较。

有没有算法或理论

编辑：对不起，我是新来的 :) 我无法说清楚。这里有一些评论会让我清楚并提出一个想法。

评论1：

实际上我知道 Levenshtein 距离，但问题是每次我比较两个字符串时，我都必须建立比较矩阵，这使得搜索过程变慢。例如，如果我可以将 hello 转换为 4444 并将 halo 转换为 4443，我可以通过索引数值来确定我对“hello”的记录有多接近。

评论 2：

也许我应该确定一个基本的恒定长度字符串并将它们的距离值存储为字符串的索引值。这只是一个想法？！

根据关于 Rabin-Karp 字符串匹配算法的维基百科条目，它可用于同时在字符串中查找几种不同的模式，同时仍保持线性复杂度。很明显，当所有模式的长度相同时，这很容易做到，但我仍然不明白如何在同时搜索不同长度的模式时保持 O(n) 复杂度。有人可以对此有所了解吗？

编辑（2011 年 12 月）：

维基百科文章已经更新，不再声称在 O(n) 中匹配多个不同长度的模式。

我只想通过表达式捕获第一个匹配项

我已经尝试过<p>.*?</p>{1}，但它不起作用它会返回 html 文档中的所有 p 标签，请帮助

我正在寻找 Hibernate 注释或 .hbm.xml，它允许我将表列指定为不区分大小写的字符串，以 unicode/utf-8/locale-independent 方式工作，适用于多个数据库引擎。

有没有这样的事情？

这样我就可以Restrictions.eq("column_name", "search_string")有效地进行查询。

我在这个结构中有一个文件：

009/foo/bar/hi23123/foo/bar231123/foo/bar/yo232131

我需要的是找到一个字符串的完全匹配；例如，在 /foo/bar/hi 和 /foo/bar/yo 中只有 /foo/bar

我想到的一种解决方案是检查输入字符串的结尾“/”。因为如果在可能的结果中有以“/”结尾的，那意味着它得到了一些不同于只有 /foo/bar 的东西。

对于这个解决方案，我必须说：

和

如何通过 Python 中的正则表达式做到这一点？

顺便说一句，如果有任何其他解决方案建议，欢迎您在这里分享。

通常我会期待一种String.contains()方法，但似乎没有。

什么是合理的检查方法？

我需要实现一个字符串匹配算法来确定哪些字符串最匹配。当可以获得这个固定长度时，我看到汉明距离是一个很好的匹配算法。

如果我改用 Levenshtein 距离公式，匹配质量有什么优势吗？我知道这种方法效率较低，因为它考虑了可变长度的字符串，但我在这里真正关心的是匹配的质量。另外，有没有更好的算法我可以考虑？如果这有什么不同，我会在 Java 中工作。

http://en.wikipedia.org/wiki/Levenshtein_distance

http://en.wikipedia.org/wiki/Hamming_distance

非常感谢

我有一个简单的 SQL 查询，

问题是所有变量字段都连接到有时为空的字段，因此我需要一种方法来使它们与它们各自的字段在它们为空时可以采用的任何值相匹配。我试过

这适用于数字字段（尽管我不喜欢像这样手动设置限制），但我不知道如何获得文本字段的通用匹配。我认为 * 会这样做，因为它匹配所有行名，但显然不是。有人知道怎么做吗？