文字列検索

簡潔データ構造第3回: 順序木に対する簡潔データ構造 (導入編)

こんにちは。レトリバのリサーチャーの木村@big_wingです。 4月から静岡県の浜松市に引っ越しをして、引き続きフルリモートで働いています。 ずいぶん久しぶりになってしまいましたが、今回は簡潔データ構造シリーズの続きで順序木に対する簡潔データ構造に…

再訪: 極大部分文字列

こんにちは。レトリバのリサーチャーの木村@big_wingです。 今回は業務で久しぶりに触れる機会があったこともあり、極大部分文字列について紹介したいと思います。 極大部分文字列については、有志の方のブログやスライドが公開されています。私も今回久しぶ…

簡潔データ構造第2.5回: ビットベクトルに対する簡潔データ構造 (select編)

こんにちは。レトリバのリサーチャーの木村@big_wingです。 前回の2回目の記事ではビットベクトルに対するrank演算を実現する簡潔データ構造を紹介しましたが、今回はselect演算を実現する簡潔データ構造を紹介します。 1回目の記事はこちらです。 2回目の記…

簡潔データ構造第2回: ビットベクトルに対する簡潔データ構造

こんにちは。レトリバのリサーチャーの木村@big_wingです。COVID-19の影響でテレワークが推進されていますが、現在私も奈良県の生駒市からフルリモートで業務を行っています。 今回は簡潔データ構造について2回目の記事で、あらゆる簡潔データ構造の基本とな…

文字列アルゴリズムは世界を救う?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 クエリの長さを…