文字列解析とマッチングアルゴリズム

Question

私は次のような問題を解決しています：

は、私はこの（のみ知られているものは、これらの名前がSOMETHING + VERSION状に形成されていることであるように、ソフトウェアパッケージとその名前のリストが見えるかもしれないがあると、バージョンは常に）名前後に来ることを意味：

Efficient.Exclusive.Zip.Archiver-PROPER.v.122.24-EXTENDED 
Efficient.Exclusive.Zip.Archiver.123.01 
Efficient-Exclusive.Zip.Archiver(2011)-126.24-X 
Zip.Archiver14.06 
Zip-Archiver.v15.08-T 
Custom.Zip.Archiver1.08 
Custom.Zip.Archiver1 

は今、私はこのリストを解析し、のみ最新バージョンを選択する必要があります各パッケージの。この例では期待される結果は次のようになります。

Efficient-Exclusive.Zip.Archiver(2011)-126.24-X 
Zip-Archiver.v15.08-T 
Custom.Zip.Archiver1.08 

---

私が使用して現在のアプローチは、次のように説明することができます：

Split the initial strings into groups by their starting letter, 
ignoring spaces, case and special symbols. 
(`E`, `Z`, `C` for the example list above) 

Foreach element { 

    Apply the regular expression (or a set of regular expressions), 
    which tries to deduce the version from the string and perform 
    the following conversion `STRING -> (VERSION, STRING_BEFORE_VERSION)` 

    // Example for this step: 
    // 'Efficient.Exclusive.Zip.Archiver-PROPER.v.122.24-EXTENDED' -> 
    // (122.24, Efficient.Exclusive.Zip.Archiver-PROPER) 

    Search through the corresponding group (in this example - the 'E' group) 
    and find every other strings, which starts from the 'STRING_BEFORE_VERSION' or 
    from it's significant part. This comparison is performed in ignore-case and 
    ignore-special-symbols mode. 

    // The matches for this step: 
    // Efficient.Exclusive.Zip.Archiver-PROPER, {122.24} 
    // Efficient.Exclusive.Zip.Archiver, {123.01} 
    // Efficient-Exclusive.Zip.Archiver, {126.24, 2011} 

    // The last one will get picked, because year is ignored. 

    Get the possible version from each match, ***pick the latest, yield that match.*** 

    Remove every possible match (including the initial element) from the list. 
} 

このアルゴリズムは、（私は仮定として）のようなもののために働く必要がありますO(N * V + N lg N * M)ここで、Mは平均文字列一致時間を表し、Vはバージョンregexpの作業時間を表します。

---

はしかし、私はよりよい解決策は多分、特定のデータ構造またはより良いマッチングアプローチは、（常にある！）があると思います。あなたが何かを提案できるかは、現在のアプローチにいくつかのメモを作る場合

は、これを実行することを躊躇しないでください。

Answer 1

これはいかがですか？

Dictionary<string,string> latestPackages=new Dictionary<string,string>(packageNameComparer); 

foreach element 
{ 
    (package,version)=applyRegex(element); 

    if(!latestPackages.ContainsKey(package) || isNewer) 
    { 
     latestPackages[package]=version; 
    } 
} 

//print out latestPackages 

ディクショナリ操作はO（1）なので、合計実行時間はO（n）です。事前にグループ化する必要はなく、すべてのマッチを保存する代わりに、現在最新のもののみを保存します。

ディクショナリには、IEqualityComparerオブジェクトを受け入れるコンストラクタがあります。そこでは、パッケージ名の間に独自の意味合いを実装することができます。しかし、このIEqualityComparerにGetHashCodeメソッドを実装する必要があることに注意してください。このメソッドは、等しいとみなすオブジェクトに対して同じ値を返す必要があります。上記の例を再現するには、文字列の最初の文字のハッシュコードを返すことができます。これは、辞書内のグループ化を再現します。しかし、衝突があまりないスマートなハッシュコードでより多くのパフォーマンスを得ることができます。それでもまだ良い結果が得られる場合は、より多くの文字を使用している可能性があります。

Answer 2

おそらくDAWG（http://en.wikipedia.org/wiki/Directed_acyclic_word_graph）を使うと良いでしょう。私はあなたが単に1つの "子供"を持っているものを打つまで、各ノードを単純にサイクルダウンすることができると思います。このノードでは、下にツリーとバージョン文字列を「上に」置いています。そこから、桁やピリオドでないものをすべて削除し、ピリオドで文字列を分割し、配列の各要素を整数に変換して、バージョン文字列を解析します。これにより、各バージョン文字列に対してint配列が得られるはずです。最高のバージョンを特定し、それを記録し、次のノードに旅行するのは1人の子供だけです。

EDIT：大規模なDAWGを移植するのは非常に高価ですが、検索は非常に高速です。