匹配不同的字符串

假設兩組字符串：匹配不同的字符串

[ "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

匹配不同的字符串

回答

相關問題