文字列「abab」は、インデックス付きシンボル「0101」のパターンと考えることができます。また、文字列「bcbc」も「0101」で表されます。これはかなり気の利いたものであり、強力な比較にはなりますが、完璧なケースではすぐに崩れてしまいます。
「babcbc」は「010202」になります。「0101」（bcbc部分）に等しいパターンが含まれていることに注意したい場合、各インデックスで何らかの正規化プロセスを実行して、比較のためにnから長さまでの部分文字列を象徴的に「再表現」することしか考えられません. そして、「babcbc」と「dababd」(010202 対 012120) に共通点があるかどうかを確認しようとすると、複雑になります。とても非効率的です！
可能なすべてのネストされたケースを処理しながら、これを効率的に行うにはどうすればよいでしょうか? 実際のテキストの類似した部分文字列ではなく、類似したパターンを探していることに注意してください。
各文字を min(K、その文字の前の発生までの距離) に置き換えてみてください。ここで、K は調整可能な定数であるため、babcbc と dababd は KK2K22 と KKK225 のようになります。接尾辞ツリーまたは接尾辞配列を使用して、変換されたテキスト内の繰り返しを見つけることができます。
Prolog の統合機能と属性付き変数を使用してテンプレートを照合するソリューションを次に示します。
:-dynamic pattern_i/3.
test:-
retractall(pattern_i(_,_,_)),
add_pattern(abab),
add_pattern(bcbc),
add_pattern(babcbc),
add_pattern(dababd),
show_similarities.
show_similarities:-
call(pattern_i(Word, Pattern, Maps)),
match_pattern(Word, Pattern, Maps),
fail.
show_similarities.
match_pattern(Word, Pattern, Maps):-
all_dif(Maps), % all variables should be unique
call(pattern_i(MWord, MPattern, MMaps)),
Word\=MWord,
all_dif(MMaps),
append([_, Pattern, _], MPattern), % Matches patterns
writeln(words(Word, MWord)),
write('mapping: '),
match_pattern1(Maps, MMaps). % Prints mappings
match_pattern1([], _):-
nl,nl.
match_pattern1([Char-Char|Maps], MMaps):-
select(MChar-Char, MMaps, NMMaps),
write(Char), write('='), write(MChar), write(' '),
!,
match_pattern1(Maps, NMMaps).
add_pattern(Word):-
word_to_pattern(Word, Pattern, Maps),
assertz(pattern_i(Word, Pattern, Maps)).
word_to_pattern(Word, Pattern, Maps):-
atom_chars(Word, Chars),
chars_to_pattern(Chars, [], Pattern, Maps).
chars_to_pattern([], Maps, [], RMaps):-
reverse(Maps, RMaps).
chars_to_pattern([Char|Tail], Maps, [PChar|Pattern], NMaps):-
member(Char-PChar, Maps),
!,
chars_to_pattern(Tail, Maps, Pattern, NMaps).
chars_to_pattern([Char|Tail], Maps, [PChar|Pattern], NMaps):-
chars_to_pattern(Tail, [Char-PChar|Maps], Pattern, NMaps).
all_dif([]).
all_dif([_-Var|Maps]):-
all_dif(Var, Maps),
all_dif(Maps).
all_dif(_, []).
all_dif(Var, [_-MVar|Maps]):-
dif(Var, MVar),
all_dif(Var, Maps).
アルゴリズムの考え方は次のとおりです。
テストの出力 (単語 abab、bcbc、babcbc、dababd):
?- test.
words(abab,bcbc)
mapping: a=b b=c
words(abab,babcbc)
mapping: a=b b=c
words(abab,dababd)
mapping: a=a b=b
words(bcbc,abab)
mapping: b=a c=b
words(bcbc,babcbc)
mapping: b=b c=c
words(bcbc,dababd)
mapping: b=a c=b
あなたのアルゴリズムでは、文字列の元のデータセットを圧縮することで情報が失われるため、元の文字列を比較するよりもはるかに多くの作業を行わずに完全な情報セットを回復できるかどうかはわかりません。また、データセットは人間が読みやすいように見えますが、現在は元の文字列と同じくらいのスペースを占めており、文字列の差分マップ (値は前の文字と現在の文字の間の距離です) には、より比較可能な情報が含まれている場合があります。設定。
ただし、すべての共通サブセットを検出する方法については、最小共通サブシーケンス アルゴリズムを調べて、最大の一致パターンを見つける必要があります。これは明確に定義されたアルゴリズムであり、効率的です。O(n * m) です。ここで、n と m は文字列の長さです。SOおよびウィキペディアのLCS を参照してください。文字列を囲むパターンも見たい場合 (円形の攪拌として -とが一致する必要があります)、Andy Nguyenによる論文で説明されている円形の LCS が必要です。abeabeabab
これまでのバリエーションの数を考慮して、アルゴリズムを少し変更する必要があります。私のアドバイスは、各文字列の圧縮バージョンと一緒に、両方の元の文字列の過去 k 文字で発生した一意の数字の数を表す 2 つの追加の次元を LCS テーブルに追加することです。次に、圧縮された文字列に一致する方向に常に移動し、過去の k 文字の両方の文字列で同じ数の一意の文字に一致する LCS ソルブを実行できます。これにより、可能な一意の部分文字列の一致がすべてエンコードされます。
トリッキーな部分は、同じ数の一意の文字を含む k を最大化する方向を常に選択することです。したがって、LCS テーブルの各要素で、k 値の最適なステップを検索する追加の文字列があります。より長いシーケンスには常にすべての可能な小さなシーケンスが含まれているため、各ステップで k の選択を最大化すると、次の反復での最良の k が最大で 1 ステップ離れていることがわかります。したがって、4D テーブルに記入すると、元の LCS テーブルと同様の方法で解決できます。4D テーブルがあるため、ロジックはより複雑になりますが、LCS の仕組みを読めば、各ステップで左上隅に向かって移動するための一貫したルールを定義する方法を理解できることに注意してください。したがって、LCS アルゴリズムは同じままで、より多くの次元にスケーリングされるだけです。
このソリューションは完成すると非常に複雑になるため、そのようなアルゴリズムの作成を開始する前に、何を達成しようとしているのか、またはこのパターンが実際に必要な情報をエンコードしているかどうかを再考することをお勧めします。