algorithm - 回文検出効率

Question

Jon Limjap のインタビュー事故に興味を持ち、回文検出を効率的に行う方法を探し始めました。回文ゴルフの回答を確認しましたが、回答には 2 つのアルゴリズムのみがあり、文字列を逆にして、テールとヘッドからチェックしているように思えます。

def palindrome_short(s):
    length = len(s)
    for i in xrange(0,length/2):
        if s[i] != s[(length-1)-i]: return False
    return True

def palindrome_reverse(s):
    return s == s[::-1]

これらの方法はどちらも、巨大な DNA 配列の正確なパリンドロームの検出には使用されていないと思います。少し調べてみましたが、これを行うための非常に効率的な方法についての無料の記事は見つかりませんでした。

良い方法は、最初のバージョンを分割統治法で並列化し、char 配列 1..n と length-1-n..length-1 のペアを各スレッドまたはプロセッサに割り当てることです。

より良い方法は何でしょうか？

何でも知ってますか？

score 7 · Accepted Answer

回文が1つしかない場合は、O（N）で実行する必要があります。あなたが言ったように文字列を分割することにより、マルチプロセッサでより効率を得ることができます。

ここで、正確なDNAマッチングを実行したいとします。これらの文字列は数千文字の長さであり、非常に反復的です。これにより、最適化する機会が得られます。

1000文字の長さの文字列を100,100の5つのペアに分割するとします。コードは次のようになります。

isPal(w[0:100],w[-100:]) and isPal(w[101:200], w[-200:-100]) ...

など...これらの試合を初めて行うときは、それらを処理する必要があります。ただし、実行したすべての結果をブール値へのハッシュテーブルマッピングペアに追加できます。

isPal = {("ATTAGC", "CGATTA"): True, ("ATTGCA", "CAGTAA"): False}

など...しかし、これはあまりにも多くのメモリを消費します。100,100のペアの場合、ハッシュマップには2 * 4^100の要素が含まれます。キーとして32ビットの文字列のハッシュを2つだけ格納するとすると、10 ^ 55メガバイトのようなものが必要になりますが、これはばかげています。

おそらく、より小さな文字列を使用する場合、問題は扱いやすい可能性があります。次に、巨大なハッシュマップが作成されますが、少なくとも10x10ペアの回文はO（1）を取るため、1000文字列が回文であるかどうかを確認すると、500回の比較ではなく100回のルックアップが必要になります。それはまだO（N）ですが...

score 3 · Accepted Answer

2 番目の関数の別のバリアント。通常の文字列と逆の文字列の右側の部分が等しいかどうかをチェックする必要はありません。

def palindrome_reverse(s):
  l = len(s) / 2
  return s[:l] == s[l::-1]

score 2 · Accepted Answer

あいまい一致を行わない限り、ありません。これはおそらく彼らが DNA で行っていることです (私はsmith-waterman を使用して DNA でEST検索を行いましたが、シーケンス内の回文または逆補数を照合するよりもはるかに難しいことは明らかです)。

score 2 · Accepted Answer

明らかに、各文字を少なくとも 1 回は検査する必要があるため、O(n) の漸近効率を超えることはできません。ただし、より良い乗法定数を取得できます。

シングルスレッドの場合は、アセンブリを使用して高速化できます。一度に 1 バイトを超えるチャンクでデータを調べることもできますが、アラインメントを考慮すると難しい場合があります。一度に 16 バイトものチャンクを調べることができる場合は、SIMD を使用する方がさらに効果的です。

並列化する場合は、文字列を N 個に分割し、プロセッサにセグメントとセグメントをi比較させることができます。[i*n/2, (i+1)*N/2)[L-(i+1)*N/2, L-i*N/2)

score 1 · Accepted Answer

どちらも O(N) にあるため、これらのソリューションのいずれにも特定の効率上の問題はないと思います。多分私は十分に創造的ではありませんが、N個の要素をN個未満のステップで比較する方法がわからないので、O(log N)のようなものは絶対に不可能です。

並列化は役立つかもしれませんが、それでもアルゴリズムの大きなランクは変わりません。これは、より高速なマシンで実行するのと同等であるためです。

score 0 · Accepted Answer

中心からの比較は、ミスを早期に回避できるため、常にはるかに効率的ですが、最大半径を探しているか、重複していないすべての回文を探しているかに関係なく、より高速な最大回文検索を行うこともできます。

唯一の本当の並列化は、処理する独立した文字列が複数ある場合です。チャンクに分割すると、ミスごとに多くの作業が無駄になり、ヒットよりもミスの方が常に多くなります。

score -1 · Accepted Answer

Python を使用すると、VM のより高速な内部に負荷がかかるため、短いコードの方が高速になります (キャッシュ全体などもあります)。

def ispalin(x):
   return all(x[a]==x[-a-1] for a in xrange(len(x)>>1))

algorithm - 回文検出効率

9 に答える 9

Related

Reference