是否有任何简单的算法来确定代表同一个人的 2 个名字的可能性？
我不是要求自定义部门可能使用的级别。只是一个简单的算法，它会告诉我“James T. Clark”是否很可能与“J. Clark”同名。托马斯·克拉克”或“詹姆斯·克拉克”。
如果有一个算法C#会很棒，但我可以翻译任何语言。
AD
问问题
1227 次
7 回答
4
听起来您正在寻找基于语音的算法，例如soundex、NYSIIS或double metaphone。第一个实际上是几个政府部门使用的，实施起来很简单（有许多现成的实施）。第二个是第一个稍微复杂和更精确的版本。后者最适用于一些非英文名称和字母。
Levenshtein 距离是两个任意字符串之间距离的定义。它为您提供相同字符串之间的距离为 0，不同字符串之间的距离为非零，如果您决定制作自定义算法，这也可能很有用。
于 2008-09-16T01:22:33.863 回答
3
Levenshtein很接近，虽然可能不是你想要的。
于 2008-09-16T01:06:39.237 回答
2
我遇到过类似的问题并尝试先使用 Levenstein 距离，但它对我来说效果不佳。我想出了一种算法，它可以为您提供两个字符串之间的“相似性”值（更高的值意味着更多相似的字符串，“1”表示相同的字符串）。这个值本身并不是很有意义（如果不是“1”，则始终为 0.5 或更小），但是当您输入匈牙利矩阵以从两个字符串列表中查找匹配对时，它的效果非常好。
像这样使用：
PartialStringComparer cmp = new PartialStringComparer();
tbResult.Text = cmp.Compare(textBox1.Text, textBox2.Text).ToString();
后面的代码：
public class SubstringRange {
string masterString;
public string MasterString {
get { return masterString; }
set { masterString = value; }
}
int start;
public int Start {
get { return start; }
set { start = value; }
}
int end;
public int End {
get { return end; }
set { end = value; }
}
public int Length {
get { return End - Start; }
set { End = Start + value;}
}
public bool IsValid {
get { return MasterString.Length >= End && End >= Start && Start >= 0; }
}
public string Contents {
get {
if(IsValid) {
return MasterString.Substring(Start, Length);
} else {
return "";
}
}
}
public bool OverlapsRange(SubstringRange range) {
return !(End < range.Start || Start > range.End);
}
public bool ContainsRange(SubstringRange range) {
return range.Start >= Start && range.End <= End;
}
public bool ExpandTo(string newContents) {
if(MasterString.Substring(Start).StartsWith(newContents, StringComparison.InvariantCultureIgnoreCase) && newContents.Length > Length) {
Length = newContents.Length;
return true;
} else {
return false;
}
}
}
public class SubstringRangeList: List<SubstringRange> {
string masterString;
public string MasterString {
get { return masterString; }
set { masterString = value; }
}
public SubstringRangeList(string masterString) {
this.MasterString = masterString;
}
public SubstringRange FindString(string s){
foreach(SubstringRange r in this){
if(r.Contents.Equals(s, StringComparison.InvariantCultureIgnoreCase))
return r;
}
return null;
}
public SubstringRange FindSubstring(string s){
foreach(SubstringRange r in this){
if(r.Contents.StartsWith(s, StringComparison.InvariantCultureIgnoreCase))
return r;
}
return null;
}
public bool ContainsRange(SubstringRange range) {
foreach(SubstringRange r in this) {
if(r.ContainsRange(range))
return true;
}
return false;
}
public bool AddSubstring(string substring) {
bool result = false;
foreach(SubstringRange r in this) {
if(r.ExpandTo(substring)) {
result = true;
}
}
if(FindSubstring(substring) == null) {
bool patternfound = true;
int start = 0;
while(patternfound){
patternfound = false;
start = MasterString.IndexOf(substring, start, StringComparison.InvariantCultureIgnoreCase);
patternfound = start != -1;
if(patternfound) {
SubstringRange r = new SubstringRange();
r.MasterString = this.MasterString;
r.Start = start++;
r.Length = substring.Length;
if(!ContainsRange(r)) {
this.Add(r);
result = true;
}
}
}
}
return result;
}
private static bool SubstringRangeMoreThanOneChar(SubstringRange range) {
return range.Length > 1;
}
public float Weight {
get {
if(MasterString.Length == 0 || Count == 0)
return 0;
float numerator = 0;
int denominator = 0;
foreach(SubstringRange r in this.FindAll(SubstringRangeMoreThanOneChar)) {
numerator += r.Length;
denominator++;
}
if(denominator == 0)
return 0;
return numerator / denominator / MasterString.Length;
}
}
public void RemoveOverlappingRanges() {
SubstringRangeList l = new SubstringRangeList(this.MasterString);
l.AddRange(this);//create a copy of this list
foreach(SubstringRange r in l) {
if(this.Contains(r) && this.ContainsRange(r)) {
Remove(r);//try to remove the range
if(!ContainsRange(r)) {//see if the list still contains "superset" of this range
Add(r);//if not, add it back
}
}
}
}
public void AddStringToCompare(string s) {
for(int start = 0; start < s.Length; start++) {
for(int len = 1; start + len <= s.Length; len++) {
string part = s.Substring(start, len);
if(!AddSubstring(part))
break;
}
}
RemoveOverlappingRanges();
}
}
public class PartialStringComparer {
public float Compare(string s1, string s2) {
SubstringRangeList srl1 = new SubstringRangeList(s1);
srl1.AddStringToCompare(s2);
SubstringRangeList srl2 = new SubstringRangeList(s2);
srl2.AddStringToCompare(s1);
return (srl1.Weight + srl2.Weight) / 2;
}
}
Levenstein 距离一要简单得多（改编自http://www.merriampark.com/ld.htm）：
public class Distance {
/// <summary>
/// Compute Levenshtein distance
/// </summary>
/// <param name="s">String 1</param>
/// <param name="t">String 2</param>
/// <returns>Distance between the two strings.
/// The larger the number, the bigger the difference.
/// </returns>
public static int LD(string s, string t) {
int n = s.Length; //length of s
int m = t.Length; //length of t
int[,] d = new int[n + 1, m + 1]; // matrix
int cost; // cost
// Step 1
if(n == 0) return m;
if(m == 0) return n;
// Step 2
for(int i = 0; i <= n; d[i, 0] = i++) ;
for(int j = 0; j <= m; d[0, j] = j++) ;
// Step 3
for(int i = 1; i <= n; i++) {
//Step 4
for(int j = 1; j <= m; j++) {
// Step 5
cost = (t.Substring(j - 1, 1) == s.Substring(i - 1, 1) ? 0 : 1);
// Step 6
d[i, j] = System.Math.Min(System.Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1), d[i - 1, j - 1] + cost);
}
}
// Step 7
return d[n, m];
}
}
于 2008-09-16T01:32:58.753 回答
0
我怀疑有，考虑到即使是海关部门似乎也没有令人满意的答案......
于 2008-09-16T01:09:21.430 回答
0
如果这个问题有解决方案，我严重怀疑它是核心 C# 的一部分。在我的脑海中，它需要一个包含名字，中间名和姓氏频率的数据库，以及首字母缩写，就像你的例子一样。这是一个相当复杂的逻辑，依赖于信息数据库。
于 2008-09-16T01:11:46.167 回答
0
仅次于 Levenshtein 距离，你想要什么语言？我能够很容易地在 codeproject 上找到 C# 中的实现。
于 2008-09-16T01:13:34.680 回答
0
在我处理的一个应用程序中，姓氏字段被认为是可靠的。因此将所有具有相同姓氏的所有记录呈现给用户。用户可以按其他字段排序以查找相似的名称。该解决方案足以大大减少用户创建重复记录的问题。
基本上看起来这个问题需要人工判断。
于 2008-09-16T01:16:07.890 回答