2

私は文字列のセットを持っており、[S1 S2 S3 ... Sn]そのようなすべてのターゲット文字列をカウントしTて、それぞれが合計の編集内S1 S2... Snで変換できるようにします。すべての文字列は固定長であり、ここでの編集はハミング距離です。TK
L

私が持っているのは、一種のブルートフォースアプローチです。したがって、アルファベットのサイズが4の場合、O（4 ^ L）のスペースをサンプリングし、それぞれをチェックするのにO（L）の時間がかかります。複雑さを指数関数からいくつかのポリまたは疑似ポリに下げることはできないようです！サンプルスペースを整理して改善する方法はありますか？

L次元のベクトル空間のように視覚化してみました。私はNポイントを与えられており、与えられたNポイントからの距離の合計がK以下であるすべてのポイントを数える必要があります。
i.e. d1 + d2 + d3 +...+ dN <= K
この問題または同様の問題をより複雑に解決する既知の幾何学的アルゴリズムはありますか？親切に私を正しい方向に向けてください。さもないとヒントをいただければ幸いです。
ありがとうございました

4

2 に答える 2

1

これは、動的計画法を使用して効率的に行うことができます。

重要なアイデアは、すべての可能なターゲット文字列を列挙する必要はないということです。Iの後の文字列インデックスのみを考慮して、K編集でターゲットが可能な方法をいくつ知っている必要があります。

alphabet = 'abcd'
s = [ 'aabbbb', 'bacaaa', 'dabbbb', 'cabaaa']

# use memoized from http://wiki.python.org/moin/PythonDecoratorLibrary          
@memoized
def count(edits_left, index):
  if index == -1 and edits_left >= 0:
    return 1
  if edits_left < 0:
    return 0
  ret = 0
  for char in alphabet:
    edits_used = 0
    for mutate_str in s:
      if mutate_str[index] != char:
        edits_used += 1
    ret += count(edits_left - edits_used, index - 1)
  return ret
于 2012-02-16T17:00:11.383 に答える
0

大声で考えると、この問題は組み合わせの問題に要約されているように私には思えます。

一般に、長さLの文字列Sの場合、置換できるC（L、K）（二項係数）位置の合計があるため、（ALPHABET_SIZE ^ K）* C（L、K）はハミングからの文字列Tをターゲットにします。 Kの距離。

二項係数は、動的計画法とパスカルの三角形を使用して非常に簡単に計算できます...階乗などに夢中になる必要はありません...

1つの文字列のケースが処理されるようになったので、複数の文字列を処理するのは、ターゲットを2倍にする可能性があるため、少し注意が必要です。直感的には、S1がS2からK離れている場合、両方の文字列が同じターゲットセットを生成するため、この場合は二重にカウントされません。この最後のステートメントはロングショットかもしれないので、私は「直感的に」と言うようにしました:)

それが役に立てば幸い、

于 2012-02-16T17:30:39.220 に答える