匹配不同的字符串

假设两组字符串：匹配不同的字符串

[ "Mr. Jones", "O'Flaherty", "Bob", "Rob Jenkins" ] 
[ "Maxwell O'Flaherty", "Robert Jenkins", "Mrs. Smith" ]

显而易见的是，这两套有麦克斯韦奥弗莱厄蒂和罗伯特·詹金斯共同点。

有什么算法可以让我们以编程方式进行这样的匹配吗？我正在考虑编写将通过字符串数组中的每个元素的内容，并尝试查找任何唯一且不包含在任何其他元素中的任何子字符串，然后将其用作每种元素的一种散列以匹配这两套。

来源

2010-11-13 devprog

您应该知道，应该将哪些名称视为相同。由于我对英文名字不熟悉，对于我来说这并不明显，“这两套有麦克斯韦奥弗莱厄蒂和罗伯特詹金斯的共同之处。”对于C＃编译器来说并不明显。至于你，“萨沙伊凡诺夫”和“亚历山大彼得罗维奇伊万诺夫”是不一样的，但不同于“阿列克谢伊凡诺夫”。 – Vovanium 2010-11-13 20:27:28

我同意，一台电脑与Sasha和Alexandr匹配的机会与匹配Richard和Dick的机会一样少。问题不是姓氏，而是简单地匹配类似的字符串。 – devprog 2010-11-14 10:15:00

可能是以下副本： [http://stackoverflow.com/questions/83777/are-there-any-fuzzy-search-or-string-similarity-functions-libraries-written-for-c](http:/ /stackoverflow.com/questions/83777/are-there-any-fuzzy-search-or-string-similarity-functions-libraries-written-for-c） – 2010-11-13 14:18:33

您可能会发现Levenshtein距离有用。如果你正在做很多这方面的事情，目前还不清楚这些信息有多准确，那么还有用于字符串消歧的库。（Rob和Robert并不“明显” - 实际上第一个可能是Robin。

来源

2010-11-13 14:27:37

我正在研究第一个答案的levenshtein距离。我明白你的观点，他们只能告诉你这些琴弦有多接近，并不能保证Rob的人性意义是罗伯特而不是罗宾。我将不得不找到一种方法来比较集合中所有元素的距离，以建立一个低于此值的平均值，而这个平均值不能被认为是匹配的。 – devprog 2010-11-13 15:38:36

如果这是真实世界的例子，并且您需要名称或姓氏的精确匹配，则解析第二个数组中的所有字符串并创建包含所有已解析的子字符串的新数组，以及存储索引到子字符串所包含的原始数组元素：

[{“Maxwell”，0}，{“O'Flaherty”，0}，{“Robert”，1} { “詹金斯”，1}，{ “太太”，2}，{ “史密斯”，2}]

现在，你可以找到精确匹配，并且知道它涉及什么人。

来源

2010-11-13 14:57:55 Dialecticus

名称和姓氏元素仅仅是一个例子，它们可以是任何字符串，所以我不想依赖于识别姓名和姓氏等单个组件。尽管感谢您的回答。 – devprog 2010-11-13 15:35:36

一方法I'v过去用于处理像罗伯特和鲍勃这样的问题是通过向可以识别相似性的互联网源进行查询。

例如，我不知道Wolfram Alpha的自动搜索策略（尽管我认为他们在某个时候正在开发API），但是搜索Robert（http://www.wolframalpha.com/input/?i=robert）会发现它应该与名字“Rob”。此外，这并不是所有的程序设计，但我发现如果您的数据集的大小受到合理限制，巧妙使用亚马逊的Mechanical Turk可以为这类问题创造奇迹。

来源

2010-11-14 17:49:39

匹配不同的字符串

回答

相关问题