配列内の各要素を互いに比較する

Question

配列の各要素をそれぞれ別の要素と比較する必要があるという点で、1次元配列を比較する必要があります。配列には、最長から最短までソートされた文字列のリストが含まれます。配列内の2つの項目は同じですが、同じ長さの項目があります。現在、N *（N + 1）/ 2の比較（1278億）を行っており、すべての比較の回数を減らそうとしています。

文字列の長さがx％以上異なっていて、等しくないと気にしないでください。また、その下の他の人も同じではないので、ループを破るだけです次の要素に移動します。

要素Aが要素CとDに一致すると、要素CとDも一致しているので、要素CとDが一致していると判断します（つまり、その操作をスキップします） 。これは私がそれを可能にするデータ構造を現在知らないので、私が考慮した限りです。

質問はここにあります：誰もそのようなデータ構造を知っていますか？または私の比較をさらに減らす方法を知っている人はいますか？

私の現在の実装は、10時間の時間枠で完了するのに3.5日かかります（時間がかかりすぎます）。残りのオプションは、実行時間を短縮するか、可能ではないか、または数十のシステム全体で作業負荷を分散しますが、実用的でない可能性があります。

更新：私の悪い。単語equalをに近いものと置き換えてください。私はLevensteinの距離を計算しています

考えてみましょう配列内の各要素と密接に一致する配列内の他の文字列があるかどうかを調べることです。出力は、密接に関連した文字列のデータベースマッピングです。

ここに、このメソッドの部分コードを示します。このコードブロックを実行する前に、アイテムをデータベースにロードするコードがあります。

public static void RelatedAddressCompute() { 
     TableWipe("RelatedAddress"); 

     decimal _requiredDistance = Properties.Settings.Default.LevenshteinDistance; 

     SqlConnection _connection = new SqlConnection(Properties.Settings.Default.AML_STORE); 
     _connection.Open(); 

     string _cacheFilter = "LevenshteinCache NOT IN ('','SAMEASABOVE','SAME')"; 

     SqlCommand _dataCommand = new SqlCommand(@" 
     SELECT 
      COUNT(DISTINCT LevenshteinCache) 
     FROM 
      Address 
     WHERE 
      " + _cacheFilter + @" 
     AND 
      LEN(LevenshteinCache) > 12", _connection); 
     _dataCommand.CommandTimeout = 0; 
     int _addressCount = (int)_dataCommand.ExecuteScalar(); 

     _dataCommand = new SqlCommand(@" 
     SELECT 
      Data.LevenshteinCache, 
      Data.CacheCount 
     FROM    
      (SELECT 
       DISTINCT LevenshteinCache, 
       COUNT(LevenshteinCache) AS CacheCount 
      FROM 
       Address 
      WHERE 
       " + _cacheFilter + @" 
      GROUP BY 
       LevenshteinCache) Data 
     WHERE 
      LEN(LevenshteinCache) > 12 
     ORDER BY 
      LEN(LevenshteinCache) DESC", _connection); 
     _dataCommand.CommandTimeout = 0; 
     SqlDataReader _addressReader = _dataCommand.ExecuteReader(); 

     string[] _addresses = new string[_addressCount + 1]; 
     int[] _addressInstance = new int[_addressCount + 1]; 
     int _itemIndex = 1; 
     while (_addressReader.Read()) { 
      string _address = (string)_addressReader[0]; 
      int _count = (int)_addressReader[1]; 
      _addresses[_itemIndex] = _address; 
      _addressInstance[_itemIndex] = _count; 
      _itemIndex++; 
     } 

     _addressReader.Close(); 
     decimal _comparasionsMade = 0; 
     decimal _comparisionsAttempted = 0; 
     decimal _comparisionsExpected = (decimal)_addressCount * ((decimal)_addressCount + 1)/2; 
     decimal _percentCompleted = 0; 
     DateTime _startTime = DateTime.Now; 
     Parallel.For(1, _addressCount, delegate(int i) { 
      for (int _index = i + 1; _index <= _addressCount; _index++) { 
       _comparisionsAttempted++; 
       decimal _percent = _addresses[i].Length < _addresses[_index].Length ? (decimal)_addresses[i].Length/(decimal)_addresses[_index].Length : (decimal)_addresses[_index].Length/(decimal)_addresses[i].Length; 
       if (_percent < _requiredDistance) { 
        decimal _difference = new Levenshtein().threasholdiLD(_addresses[i], _addresses[_index], 50); 
        _comparasionsMade++; 
        if (_difference <= _requiredDistance) { 
         InsertRelatedAddress(ref _connection, _addresses[i], _addresses[_index], _difference); 
        } 
       } 
       else { 
        _comparisionsAttempted += _addressCount - _index; 
        break; 
       } 
      } 
      if (_addressInstance[i] > 1 && _addressInstance[i] < 31) { 
       InsertRelatedAddress(ref _connection, _addresses[i], _addresses[i], 0); 
      } 
      _percentCompleted = (_comparisionsAttempted/_comparisionsExpected) * 100M; 
      TimeSpan _estimatedDuration = new TimeSpan((long)((((decimal)(DateTime.Now - _startTime).Ticks)/_percentCompleted) * 100)); 
      TimeSpan _timeRemaining = _estimatedDuration - (DateTime.Now - _startTime); 
      string _timeRemains = _timeRemaining.ToString(); 
     }); 
    } 

InsertRelatedAddressは、データベースを更新する関数であり、配列には500,000個のアイテムがあります。

Answer 1

OK。更新された質問で、私はそれがより理にかなっていると思う。 Levenshtein Distanceがあらかじめ設定された距離より小さい文字列のペアを探したいとします。私は、あなたが設定した制限内で文字列を検索するために、すべての文字列を比較せず、Levenshtein距離のプロパティに頼っていることが重要だと思います。答えには、可能な変更のツリーを計算することが含まれます。つまり、距離< nで指定された文字列の可能な変更を計算し、それらの文字列のいずれかがセットに含まれているかどうかを確認します。 nが小さければ、これはほんの高速です。

ここに投稿された質問のようです：Finding closest neighbour using optimized Levenshtein Algorithm。

Answer 2

詳細情報が必要です。あなたの望む結果は何ですか？すべての一意の文字列を取得しようとしていますか？あなたは、2つの文字列が等しいかどうか、そして '長さがxパーセントで違うなら、それらが等しくないと気にしないでください。長さの制約をxパーセントで調べているのはなぜですか？彼らが同じであることを確認している場合は、同じ長さでなければなりません。 正確な一致を判断するのに少し違うことをしようとしていると思われます。 ありがとう ニール