4

標準ライブラリが 2 つの文字列間の距離を計算するものを提供しているとは思わず、Boost StringAlgo には何も見つからないようです。それで、私が使用できる他のライブラリはありますか？

私はアルゴリズムについてあまりうるさいわけではありません。Jaro-Winkler は問題ありません。Levenshtein も同様です。私は提案を受け付けています。誰かが既にコーディングしたものをコーディングしたくありません。

4

3 に答える 3

8

実際の距離メトリックで質問を定義しないので、「メトリック（数学）」の条件を満たす必要があると思います。

セットXのメトリックは、関数（距離関数または単に距離と呼ばれます）d：X×X→R（Rは実数のセット）です。Xのすべてのx、y、zについて、この関数は次の条件を満たす必要があります。

  • d（x、y）≥0（非負性または分離公理）
  • d（x、y）= 0 x = y（不可識別者同一性、または偶然の一致の公理）の場合のみ
  • d（x、y）= d（y、x）（対称性）
  • d（x、z）≤d（x、y）+ d（y、z）（劣加法性/三角不等式）。

d次のように定義するとします。

          { 0 if x = y
d(x, y) = {
          { 1 otherwise

したがって、最初の3つの条件が満たされます。

  • d(x, y) ≥ 0
  • d(x, y) = 0 iff x = y
  • d(x, y) = d(y, x) = 0 for x = y、 とd(x, y) = d(y, x) = 1 for x ≠ y

最後の条件には、次の2つのケースがあります。

  • d(x, z) = 0。右側の考えられる値は、、、0および1であり2、いずれも条件を満たすことになります。
  • d(x, z) = 1。右側が1以上ではないとします。これは、ゼロでなければならないことを意味します。次に、右側の両方の用語はそれぞれ0である必要があります。つまり、x = yとy = zです。2番目の条件は、を意味します。x = zこれは、を意味しd(x, z) = 0ます。これは矛盾しているので、右側は1以上でなければなりません。

次に、メトリックを次のように定義できます。

int d(std::string x, std::string y) {
    if (x == y) {
        return 0;
    } else {
        return 1;
    }
}
于 2013-02-28T14:13:03.077 に答える
6

SimStringを試すことができます。

SimString は、おおよその文字列を高速に取得するための単純なライブラリです。近似文字列検索では、クエリ文字列との類似度がしきい値以上であるデータベース内の文字列を検索します。同一文字列だけでなく、類似文字列を検索する近似文字列検索には、スペル修正、柔軟な辞書照合、重複検出、レコード リンケージなど、さまざまな用途があります。

SimString は、類似度の尺度としてコサイン、ジャカード、ダイス、およびオーバーラップ係数をサポートします。SimString は、文字列の類似性を計算するための機能として文字 n-gram を使用します。

またはSimMetricライブラリ。

SimMetrics は、編集距離 (Levenshtein、Gotoh、Jaro など) から他のメトリック (Soundex、Chapman など) までの類似度メトリック ライブラリです。EPSRCが後援するIRC（AKT）が資金を提供する英国シェフィールド大学が提供する研究、助成金番号GR / N15764 / 01。

または、Levenshtein、Dameru、Needleman-Wunsch、Hamming、Bloom Filter、Jaccard、および Minkowski 距離の実装を含む libdistanceライブラリ。

音声アルゴリズムも興味深いかもしれません。

于 2013-02-28T15:19:54.297 に答える
0

この関連する質問には、レーベンシュタイン距離を示すコード スニペットが含まれています。これは、この C コードで MySQL にも実装されています。

于 2013-02-28T15:18:54.877 に答える