4

この特定の問題に取り組むための最良の方法と、ライブラリがあるかどうか疑問に思っています（Pythonが望ましいですが、必要に応じて柔軟に対応できます）。

各行に文字列が含まれるファイルがあります。各行で最も長い一般的なパターンとその位置を見つけたいと思います。SequenceMatcherを使用して、1行目と2行目、1行目と3行目などを比較し、結果を相関させることができることは知っていますが、すでにそれを行っているものがある場合はどうでしょうか。

理想的には、これらの一致は各行のどこにでも表示されますが、初心者の場合は、各行の同じオフセットに存在し、そこから進んでいくことができます。文字列テーブルにアクセスするための優れたAPIを備えた圧縮ライブラリのようなものが理想的かもしれませんが、その説明に適合するものは今のところ見つかりません。

たとえば、次の行を使用します。

\x00\x00\x8c\x9e\x28\x28\x62\xf2\x97\x47\x81\x40\x3e\x4b\xa6\x0e\xfe\x8b
\x00\x00\xa8\x23\x2d\x28\x28\x0e\xb3\x47\x81\x40\x3e\x9c\xfa\x0b\x78\xed
\x00\x00\xb5\x30\xed\xe9\xac\x28\x28\x4b\x81\x40\x3e\xe7\xb2\x78\x7d\x3e

同じ位置にあるすべての行で0-1と10-12が一致し、line1[4,5]がline2[5,6]と一致してline3[7,8]と一致することを確認したいと思います。

ありがとう、

4

2 に答える 2

2

各行で同じオフセットにある共通の部分文字列を見つけることだけが必要な場合は、次のようなものが必要です。

matches = []
zipped_strings = zip(s1,s2,s3)
startpos = -1
for i in len(zipped_strings):
  c1,c2,c3 = zipped_strings[i]
  # if you're not inside a match, 
  #  look for matching characters and save the match start position
  if startpos==-1 and c1==c2==c3:
    startpos = i
  # if you are inside a match, 
  #  look for non-matching characters, save the match to matches, reset startpos
  elif startpos>-1 and not c1==c2==c3:
    matches.append((startpos,i,s1[startpos:i]))
    # matches will contain (startpos,endpos,matchstring) tuples
    startpos = -1
# if you're still inside a match when you run out of string, save that match too!
if startpos>-1:
  endpos = len(zipped_strings)
  matches.append((startpos,endpos,s1[startpos:endpos]))

場所に関係なく最長の共通パターンを見つけるには、SequenceMatcher が最良のアイデアのように思えますが、string1 と string2 を比較してから string1 と string3 を比較して結果をマージしようとする代わりに、string1 と string2 のすべての共通部分文字列を取得します (get_matching_blocks を使用)。 、次にその各結果を string3 と比較して、3 つの文字列すべての一致を取得します。

于 2011-06-15T21:56:41.300 に答える
0

問題はパフォーマンスですか？

あなたのインプットはどれくらいですか？

一致する文字列の長さの最小値は 2 ですか?

あなたの例は正しくないことに注意してください。期待する結果が、提供したサンプル文字列と一致しないと思います。

于 2010-04-02T14:33:49.917 に答える