按距離最小的標記排序列表

我想排序字符串列表。我有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

按距離最小的標記排序列表

回答

相關問題