文字列検索

文字列アルゴリズムは世界を救う?Suffix Array と Longest Common Substrings

COVID-19の遺伝子配列をターゲットに、Suffix Arrayを使ってLongest Common Substringsを求めてみました。また、そのアルゴリズムを解説します。

文字列検索の話(その1): ナーイブ検索と KMP法 BM法

2018/10/02の文字列検索についてのセミナーのフォローアップ記事、連載の一回目です。初回はインデックスを使わない検索、ナイーブな実装や、KMP法とBM法について書いています。

簡潔データ構造ってなに?

今回から簡潔データ構造という高速でメモリ効率のよいデータ構造について紹介していきます! 初回の今回は簡潔データ構造の定義について紹介します ∪・ω・∪

bit vectorで編集距離の計算を高速化する

MathJax.Hub.Config({ tex2jax: { inlineMath: [ ['$','$'], ['\\(','\\)'] ] } }); レトリバ製品開発部の@ysk24okです。 本記事ではbit vectorを用いて編集距離の計算を高速化するアルゴリズムを紹介します。論文はこちらです。 dl.acm.org クエリの長さを…