6

特定のパターンで 3 つの行を入力し、列を一番下までドラッグすると、Excel の機能がわかります。Excel はパターンを続行しようとします。

例えば

タイプ...

  • テスト-1
  • テスト-2
  • テスト-3

Excel は次のように続けます。

  • テスト-4
  • テスト-5
  • テスト...

日付などの他のパタ​​ーンでも同じように機能します。

同様のことを達成しようとしていますが、次のようなより例外的なケースも処理したいと考えています。

  • テストブルーサムシングエルス
  • テスト-黄色-何か他のもの
  • テストレッドサムシングエルス

このエントリに基づいて、パターンは次のようになります。

  • テスト-[動的]-何か

[DYNAMIC] を他の色で継続するのはまったく別の取引です。今はあまり気にしません。パターン内の [DYNAMIC] 部分を検出することに主に関心があります。

多数のプール エントリからこれを検出する必要があります。この種のパターンを持つ 10,000 個の文字列があり、類似性に基づいてこれらの文字列をグループ化し、テキストのどの部分が常に変化しているかを検出したいとします ([DYNAMIC])。

このシナリオではドキュメントの分類が役立ちますが、どこから始めればよいかわかりません。

アップデート：

複数の[DYNAMIC]パターンを持つことも可能であることを忘れていました。

そのような：

  • test_[動的] 12 [動的2]

重要ではないと思いますが、これを .NET に実装する予定ですが、使用するアルゴリズムに関するヒントは非常に役立ちます。

4

4 に答える 4

2

フォームのパターンの動的部分を見つけることを検討し始めるとすぐに、 <const1><dynamic1><const2><dynamic2>....他の仮定がなければ、提供したサンプル文字列の最長共通部分列を見つける必要があります。たとえば、私が持っている場合test-123-abc、test-48953-defgLCS はtest-andになり-ます。動的部分は、LCS の結果間のギャップになります。次に、適切なデータ構造で動的部分を検索できます。

2 つ以上の文字列の LCS を見つける問題は非常にコストがかかり、これが問題のボトルネックになります。精度を犠牲にして、この問題を扱いやすくすることができます。たとえば、文字列のすべてのペア間で LCS を実行し、同様の LCS 結果を持つ文字列のセットをグループ化できます。ただし、これは一部のパターンが正しく識別されないことを意味します。

もちろん、フォームのパターンのみを許可しているように見える Excel のように、文字列にさらに制限を課すことができれば、これはすべて回避できます<const><dynamic>。

于 2009-09-07T14:27:58.083 に答える
0

信じられないかもしれませんが、Googleドキュメントはこの種のことに優れているよりも優れている可能性があります。

Googleは、セットに関する大量のデータを収集しました。たとえば、指定した例では、セットの「色」の一部として青、赤、黄色を認識します。Excelよりもはるかに完全なパターン認識を備えているため、パターンを継続する可能性が高くなります。

于 2009-09-07T13:36:48.763 に答える
0

必要なのは、レーベンシュタイン距離のようなものを計算し、類似した文字列のグループを見つけてから、類似した文字列の各グループで、典型的なdiffのようなアルゴリズムで動的部分を識別することだと思います。

于 2009-09-07T12:39:12.950 に答える
0

[動的] を見つけることはそれほど大したことではありません。2 つの文字列を使用してそれを行うことができます。最初から開始し、等しくない状態になったら停止し、最後から同じことを行うと、ほら、[動的] が得られます。

(疑似コード - ちょっと) のようなもの:

String s1 = 'asdf-1-jkl';
String s2= 'asdf-2-jkl';
int s1I = 0, s2I = 0;
String dyn1, dyn2;
for (;s1I<s1.length()&&s2I<s2.length();s1I++,s2I++)
  if (s1.charAt(s1I) != s2.charAt(s2I))
    break;
int s1E = s1.length(), s2E = s2.length;
for (;s2E>0&&s1E>0;s1E--,s2E--)
  if (s1.charAt(s1E) != s2.charAt(s2E))
    break;
dyn1 = s1.substring(s1I, s1E);
dyn2 = s2.substring(s2I, s2E);

10k データセットについて。パターン (10k x 10k 呼び出し) を把握するには、各組み合わせでこれ (またはもう少し最適化されたバージョン) を呼び出す必要があります。次に、結果をパターンで並べ替えます (つまり、開始と終了を保存し、これらのフィールドで並べ替えます)。

于 2009-09-07T12:23:03.763 に答える