0

文字列のリストをソートしたい。1000 個のアドレスがあります (スペースで区切られたカスタム アドレス データ)。2 つ目は検索クエリです。ここで、すべての単語トークン (数字なし) を取得し、最小距離で並べ替えたいと思います。

例えば

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の場合、 と の間の距離は 0、 と の間HAMの距離は 2 ( 2 文字以上あるため) などです。HAMHAMHAMERHAMER

「単語」トークンを取得します。

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 :)

4

2 に答える 2

2

レーベンシュタイン距離–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-28T10:02:48.813 に答える
1

これがあなたが探しているものだと思います：

    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代わりにContains.

于 2012-08-28T10:06:10.550 に答える