文法圧縮を応用したハミング距離計算の高速化

書誌事項

タイトル別名
  • Faster Calculating Algorithm for the Hamming Distance Using Grammar Compression
  • ブンポウ アッシュク オ オウヨウ シタ ハミング キョリ ケイサン ノ コウソクカ

この論文をさがす

抄録

<p>We propose a faster calculating algorithm for the Hamming distance using grammar compression. We search substrings which the Hamming distance with a query is less than d. ESP-index[10] is a self-index based on grammar compression. ESP-index builds a derivation tree by an input string. Matching node in a tree can ensure that some characters is same. Using the property, we reduce time that calculating of the Hamming distance.</p>

収録刊行物

詳細情報

問題の指摘

ページトップへ