按距离最小的标记排序列表

我想排序字符串列表。我有1000个地址（一些用空格分隔的自定义地址数据）。第二件事是我的搜索查询。现在我想要获取所有的单词标记（不包括数字）并按最小的距离对它们进行排序。按距离最小的标记排序列表

例如

string query = "123 HAM"; 
// 1. get only "HAM" token 
// 2. count distances 
// 3. sort by them 
//distance("HAM", "12 HAM DRIVE") -> 0 
//distance("HAM", "13 HAM DRIVE") -> 0 
//distance("HAM", "14 HAMER DRIVE") -> 2 
//distance("HAM", "37 HAMMERSMITH AVENUE") -> 8

如果我的查询令牌HAM，然后HAM和HAM之间的距离是0，HAM和HAMER之间是2（因为HAMER有2个字母以上）等

我得到 '字' 令牌：

private static IEnumerable<string> GetLetterTokens(string location) 
{ 
    string[] words = location.Split(new[] {' '}, StringSplitOptions.RemoveEmptyEntries); 
    return words.Where(word => Regex.IsMatch(word.Trim(), @"^[a-zA-Z]+$")); 
}

现在对于每个地址我想要计算这些距离并按它们排序。有没有快速的方法来做到这一点？我的意思是使用List<>.Sort。

THX的建议:)

来源

2012-08-28 Nickon

指定距离，我只能看到字符串。 '“123 HAM”'表示_“HAM”_的距离是“123 whatever”？ –

我的距离是查询令牌与地址字符串中包含该令牌的单词之间的字母差异。如果我的查询令牌是“HAM”，那么HAM和HAM之间的距离= 0，HAM和HAMER之间的距离= 2（因为HAMER有2个字母以上）等。我的查询可以包含许多不同的单词，但我需要为了只得到单词（没有数字），那么我需要从查询中找到包含令牌的单词（如果令牌是“HAM”，那么所有匹配“HAM”的单词匹配），那么我需要计算距离并进行排序他们:)有点奇怪，但它应该看起来像这样。 – Nickon

我认为你可以使用[Levenshtein Distance]（http://www.dotnetperls.com/levenshtein） –

我认为这是你在找什么：

string token = "HAM"; 
    List<string> addresses = new List<string> 
    { 
     "12 HAM DRIVE", 
     "13 HAM DRIVE", 
     "14 HAMER DRIVE", 
     "37 HAMMERSMITH AVENUE", 
     "15 HAM HAMER DRIVE", 
    }; 

    var result = from a in addresses 
       let tokens = GetLetterTokens(a) 
       let distances = from t in tokens 
           where t.Contains(token) 
           select t.Length - token.Length 
       where distances.Any() 
       let distance = distances.Min() 
       orderby distance 
       select new 
       { 
        Address = a, 
        Distance = distance, 
       };

如果你只需要以令牌开始的记号，使用StartsWith inst ead的Contains。

来源

2012-08-28 10:06:10

正是我在找的东西：D工作得很好。你有什么想法如何修改它一点？代替获得一个令牌“HAM”，我会得到一个令牌列表，例如{“HAM”，“道路”，“AVEN”}。现在，我想按照“HAM”的顺序进行排序，之后会收到“ROAD”组（我说的组是指距离相同的组），最后是“AVEN”。这将是我可以在这里做的一切。 – Nickon

好的，nvm。我做到了:) Thx寻求帮助。 – Nickon

还有一个问题。有时距离不能计数，因为所有的令牌都不能包含我们的查询令牌。如何跳过这些情况？ – Nickon

我认为你可以使用Levenshtein Distance - LB

var result = addresses.OrderBy(a => 
     string.Join(" ", GetLetterTokens(a)) 
     , new LevenshteinDistance()); 

public class LevenshteinDistance : IComparer<String> 
{ 
    /// <summary> 
    /// Compute the distance between two strings. 
    /// </summary> 
    public int Compare(string s, string t) 
    { 
    int n = s.Length; 
    int m = t.Length; 
    int[,] d = new int[n + 1, m + 1]; 

    // 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 
     int cost = (t[j - 1] == s[i - 1]) ? 0 : 1; 

     // Step 6 
     d[i, j] = Math.Min(
      Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1), 
      d[i - 1, j - 1] + cost); 
     } 
    } 
    // Step 7 
    return d[n, m]; 
    } 
}

来源

2012-08-28 10:02:48

按距离最小的标记排序列表

回答

相关问题