(この質問は音楽に関するものではありませんが、ユースケースの例として音楽を使用しています。)
音楽では、フレーズを構造化する一般的な方法は、中間部分が 1 回以上繰り返される音符のシーケンスです。このように、フレーズはイントロ、ループパート、アウトロで構成されています。以下に一例を示します。
[ E E E F G A F F G A F F G A F C D ]
イントロが [ EEE ] 繰り返し部分が [ FGA F ] で、アウトロが [ CD ] であることが「わかります」。したがって、リストを分割する方法は次のようになります
[ [ E E E ] 3 [ F G A F ] [ C D ] ]
ここで、最初の項目はイントロ、2 番目の繰り返し部分の繰り返し回数、3 番目の部分はアウトロです。
このような分割を実行するアルゴリズムが必要です。
ただし、リストを分割する方法が複数ある可能性があるという注意点が 1 つあります。たとえば、上記のリストは次のように分割できます。
[ [ E E E F G A ] 2 [ F F G A ] [ F C D ] ]
しかし、これはイントロとアウトロが長いため、より悪い分割です。したがって、アルゴリズムの基準は、ループ部分の長さを最大にし、イントロとアウトロを合わせた長さを最小にする分割を見つけることです。つまり、正しい分割
[ A C C C C C C C C C A ]
は
[ [ A ] 9 [ C ] [ A ] ]
イントロとアウトロを合わせた長さは2で、ループ部分の長さは9です。
また、イントロとアウトロは空にすることができますが、「真の」繰り返しのみが許可されます。したがって、次の分割は許可されません。
[ [ ] 1 [ E E E F G A F F G A F F G A F C D ] [ ] ]
シーケンスの最適な「圧縮」を見つけることと考えてください。一部のシーケンスでは繰り返しがない場合があることに注意してください。
[ A B C D ]
これらの退化したケースでは、適切な結果が許容されます。
アルゴリズムの私の実装は次のとおりです。
def find_longest_repeating_non_overlapping_subseq(seq):
candidates = []
for i in range(len(seq)):
candidate_max = len(seq[i + 1:]) // 2
for j in range(1, candidate_max + 1):
candidate, remaining = seq[i:i + j], seq[i + j:]
n_reps = 1
len_candidate = len(candidate)
while remaining[:len_candidate] == candidate:
n_reps += 1
remaining = remaining[len_candidate:]
if n_reps > 1:
candidates.append((seq[:i], n_reps,
candidate, remaining))
if not candidates:
return (type(seq)(), 1, seq, type(seq)())
def score_candidate(candidate):
intro, reps, loop, outro = candidate
return reps - len(intro) - len(outro)
return sorted(candidates, key = score_candidate)[-1]
それが正しいかどうかはわかりませんが、説明した簡単なテストには合格しています。それに関する問題は、それが遅くなることです。接尾辞ツリーを見てきましたが、私が求めている部分文字列は重複せず隣接している必要があるため、それらは私のユースケースに適合していないようです。