LINEヤフーの研究開発

Publications

カンファレンス (国内) Renga Street: Top-kクエリ処理アルゴリズムによる高速類似文字列検索の実装

山城 颯太

言語処理学会第32回年次大会 (NLP2026)

2026.3.9

類似文字列検索は，あらかじめ与えられた文字列集合のうちから，入力クエリ文字列に類似した文字列集合を返却するタスクであり，古くから研究され続けている． 既存手法の多くは，類似性尺度として編集距離，あるいは文字N-gram素性（Q-gram）のcosine係数やJaccard係数を使用しており，各素性ごとの重みを同一と見なしている． しかし，出現頻度がべき乗則に従う自然言語を対象とする場合は，BM25のように低頻度素性を重視するスコアリング手法を用いることで，文字列同士の比較回数削減と精度向上が見込める． 本研究は類似文字列検索タスクを複数タームに基づくOR検索として定式化し直し，Top-kクエリ処理手法の一つであるMaxScoreアルゴリズムを使用することで，高速かつ正確にTop-k類似文字列が取得できることを確認した．

Paper : Renga Street: Top-kクエリ処理アルゴリズムによる高速類似文字列検索の実装新しいタブまたはウィンドウで開く （外部サイト）