ターゲット文字列との違いに基づいて文字列のリストをソートする最良の方法は？

Question

リスト内の文字列とターゲット文字列の違いに基づいてリストをソートする必要があります。

この種のソートアルゴリズムを実装する最良の方法は何ですか？

パフォーマンスはあまり気にしませんが、コレクションが大きくなる可能性があります（50万円のトップ）。

ヘルプありがとうございました！

Answer 1

Levenshtein distanceを計算し、整数結果で並べ替えることをお勧めします。 （Magic code）

public void Example() 
{ 
    string target = "target"; 

    List<string> myStings = new List<string>(); 

    myStings.Add("this"); 
    myStings.Add("that"); 

    myStrings = myStrings.OrderBy(each => Levenshtein(each, target)).ToList(); 
} 

public int Levenshtein(string stringA, string stringB) 
{ 
    // Magic goes here 
    return 0; 
} 

古いskool 2.0のユーザーのためのOrderByはありませんか？

List<string> myStrings; 
myStrings.Sort(LevenshteinCompare); 
... 

public class LevenshteinCompare: IComparer<string> 
{ 
    public int Compare(string x, string y) 
    { 
     // Magic goes here 
    } 
} 

Answer 2

ソートアルゴリズムのこの種を実装するための最良の方法は何ですか？

クイックソートのライブラリ実装を使用して、ターゲット文字列との距離をソートキーとして使用することをおすすめします。

もちろん、役に立つ回答ではありません。何故なの？あなたが本当に知りたいのは、 "文字列のメトリックはどういう意味ですか？"

の答え qusetionは、悲しげに「依存しています」。あなたが気にする距離の特性に依存します。

言われているように、Levenstein Distanceと実際に弦について言われるものを読んでください。

基本的なアルゴリズムを変更して、ダイナミックプログラミングマトリックスの異なるステップの重み付けを行うことで、ロングランで発生する同一文字を優先してメトリックを歪めることができます。

Soundexアルゴリズムを使用することもできます。これは、どの文字列が似ているかを示しています（短い文字列に最適ですが、使用する入力の種類はわかりません）。

文字列の長さが等しい場合は、ハミング距離（文字列が異なるインデックスの数を数えます）を使用することもできます。それはおそらく何かに一般化することができます（一方的に）存在しないインデックスを常に異なるものとして数えることによって、Levensteinのようなものが得られます。

短いバージョン：それは依存します。私はいくつかの情報を入力しましたが、どちらが良い選択であるかはわかりませんあなたからの情報はありません。