generated at
本当に役立つFAQ検索システムを目指して
Nota Tech Conf 2021 Spring 3日目の発表資料です
2021/3/11


こんばんは
daiizdaiizです
Helpfeelの検索技術の話をします

開発、運用チーム
プロダクトオーナー
daiiz
プロジェクトマネージャー
akix
Webディレクター
akix など
テクニカルライター
カスタマーサクセス
エンジニア、デザイナー
rakusaiakixdaiizshokaitakeruTiro


予測検索 Helpfeel
CTO 増井俊之展開ヘルプをベースとするFAQ検索システム
テキパキと高速に検索できている
クエリの表現に合わせて柔軟に結果が提示される

Agenda
いかにして探すか
1. 入力に対して遅延なく検索結果を返す
2. 結果一覧に提示する記事タイトル表現の選び方
3. 効率よく曖昧検索する
ヒット率を高めるデータセットの作り方
4. 効率よく言い換え表現を量産する技術

動画

クライアントで快適に検索処理を実行するためには必要不可欠
重いタスクを別のスレッドに移譲して、UIスレッドの負荷を軽減する
postMessage
js
// Window const worker = new Worker('worker.js') worker.onmessage = event => { // WebWorkerからの応答を受信 } worker.postMessage(data)

js
// DedicatedWorkerGlobalScope self.addEventListener('message', event => { // ここでタスクを処理 // clientに返信 self.postMessage({result: ''}) })


検索頻度の制御
タスクが積まれ過ぎて実行待ち増えすぎないよう注意する
検索頻度の制御に失敗すると?
onInputやonMessageで受けるイベントがじわじわ遅れていく
イベント発火のタイミング
ブラウザ内部のtask queueから取り出されたとき


「文字入力→検索処理→結果の表示」の一連の処理をひとつの塊と考える
検索処理の途中で入力されたクエリを無視する
workerが空いたときに最新のクエリで検索する
つねに一件の検索だけ実行される
不要なタスクの実行を極力避けられる
結果一覧のDOMの描画更新までを見届ける
workerだけでなく、UIスレッドの描画タスクの状況にも気を配る
検索タスクが間引かれる様子
UIスレッド側に、workerに発行するタスクを管理する仕組みを独自に実装した


Helpfeelでは、一つの回答記事に対して複数の「言い換え表現」が紐付いている
このページに記述するメタデータの例
? 画像間の関連情報を辿って探す
? 芋蔓的に画像を辿る
? 記憶を辿って芋蔓検索する
? 思い出の写真を探す
「記憶」「思い出」「辿る」「探す」などのキーワードでヒットできる

もう少し文字大きいほうがいいかも(ブラウザウィンドウを小さくする)shokai
良さそうですstatakker

データセット
検索のためにクライアントに送信されるデータ
展開されたすべての言い換え表現が含まれている
クエリに最もマッチする title を探す
helpdata.json
{ "faqs": [ { "pageId": "001", "title": "画像間の関連情報を辿って探す", "verbs": {...} }, { "pageId": "001", "title": "芋蔓的に画像を辿る", "verbs": {...} }, { "pageId": "001", "title": "記憶を辿って芋蔓検索する", "verbs": {...} }, // ... ], // ... }
この他、動詞、重要キーワードや読み仮名の情報も入っている
結構たくさん情報送ってるんですね。どれくらいの量で重くなるんだろうwsawachin
結果リストでは title を提示する
どの表現を選ぶかが重要になってくる
ユーザーの用いた検索語をできるだけそのまま反映させたい


動詞を探す
受け取ったクエリが、動詞かそれ以外であるかを字面から判定する
クエリに対して形態素解析は行っていない
動詞は活用される
クエリ中の活用された動詞を基本形に正規化する
撮りたい → 撮る
撮った → 撮る
撮れない → 撮れる
以降はこの基本形を持つエントリを探せばよい
活用語尾を意識した文字列探索を行わずに済む


ハイライト
ヒット箇所が動詞の場合、語幹だけでなく活用語尾まで着色する
視覚的な安定性があり、瞬時に理解しやすい

データセットで faqs verbs にて動詞の活用語尾を持つ
基本形と活用形を全て生成している
活用語尾は規則的に変化するので機械的に処理しやすい
helpdata.json
{ "verbs": { "撮る": [ "撮ら", "撮り", "撮る", "撮れ", "撮ろ", "撮っ" ], "撮れる": [ "撮れ", "撮れる", "撮れれ", "撮れろ", "撮れよ" ] }, "verbGroups": [ ["撮る", "撮れる"] ], "faqs": [ { "title": "スクショが撮れない", verbs: { "撮れる": ["撮れ"] } }, { "title": "スクショを撮りたい", verbs: { "撮る": ["撮り"] } }, { "title": "スクショを撮る方法", verbs: { "撮る": ["撮る"] } } ] }
基本形に正規化された動詞を持つエントリを絞り込む
同時に活用された表記も取得できる


重要度が高い単語をハイライト
文字入力する度に更新される
自然文を入力とするHelpfeel Contactでの実装
ColoredTextLayer
<textarea> 要素で下線ハイライト機能付きの入力欄を実現するReact Componentを作った
textarea要素の背景に、borderを表示するための <div> 要素を配置
このdiv要素に、textareaの内容を透明色の文字として表示し、この文字列に対してborder-bottomを与える
線の位置を正確に特定するため、フォントや文字サイズ、折り返し等もそのまま反映させる
html
<div className='query-textarea-container'> <textarea className='query-textarea' /> <ColoredTextLayer text={sentence} hits={hits} /> </div>
css
div.colored-text-layer, textarea.query-textarea { /* ... */ font-size: 16px; font-weight: 400; font-family: sans-serif; /* textareaと下層のdivとで文字位置を揃える設定 */ word-break: break-word; font-kerning: none; font-variant-ligatures: none; }
データセットに含まれる単語群のうち、線を引くべき重要度が高い語がworkerから返される


重要度が高い語の推定
動詞に重きをおいて探す
文章全体で保持する結果
_hitVerbs : ヒットした動詞の情報
_hitRareWords : ヒットした希少度の高いレアな自立語
一文 text ずつ解析する
これまでの文章でヒットした語と、対象のテキストを渡す
js
// hits: textareaで下線ハイライトする語の表層形 const { faqInfos, hits, hitVerbs, hitRareWords, hitBaseForms } = searchBySentence(text, { prevVerbs: _hitVerbs, // ポイント: 後続の文の解析でも参照する prevWords: _hitRareWords })
一文を受け取って検索する関数
動詞を抽出し、回答候補を探す
prevVerbsも含めて、抽出した動詞を出現頻度が低い順にソートする
続いて動詞以外の自立語で探す
工夫
自然文を受け取るので、意味のある動詞が含まれるという仮説
基本的には一つのことについて書かれているはずなので、直前までの内容も重要
データセット構築時に名詞や動詞を希少度が高い順にソートしている
tf-idf的な考え方


曖昧検索
正規表現では記述できないような曖昧な表現で検索したい
→ 曖昧度 (編集距離) を許容した文字列マッチを実現したい
うろ覚えな言葉やスペルミス、表記ゆれを吸収できる
ディスクトップ、ハードデスク
Andoid、Gyozo、Scarpbxo
インターフェース、インタフェイス
愚直に文字列比較を繰り返すのは大変


曖昧検索のアルゴリズム
効率の良い手法が存在する
Bitapアルゴリズム (shift-and、shift-orアルゴリズム)
bit-parallel approximate pattern matching
Baeza-Yates, Ricardo A.; Gonnet, Gastón H. (1992). “A New Approach to Text Searching"
特徴
ビット演算の並列性を利用した文字列探索アルゴリズム
編集距離に基づいた類似文字列の検索を行える


曖昧さ
余計な文字の混入
文字を間違えている
文字が足りない
ビットシフト演算と論理演算だけで高速に実行できる
曖昧検索ライブラリ
Scrapboxでの検索でも使っている


文字列マッチ問題は、NDFAで受理されるか?と考える
一文字認識されるたびに次の状態に遷移する
遷移先の選択肢が一意でなくてもよい
この特性を活かして曖昧さを込めた文字列の一致判定を実現できる
最終的に受理状態のノードに到達したらマッチ成功
曖昧度ゼロ (完全一致) の場合の状態遷移機械
パタン「daiiz」を認識する状態遷移機械


曖昧度を持つ文字列マッチをNDFAで表現する
クエリ「taiz」がパタン「daiiz」に曖昧度2でマッチする様子
*: 任意の文字
ε: 空文字
asearchでは、この状態遷移を少ないメモリで実行できる

曖昧性と遷移の対応
余計な文字の混入
daxiiz
上に遷移
文字を間違えている
dajiz
右上に遷移
文字が足りない
daiz
右上に遷移
一致時
横方向に遷移

曖昧度3でマッチする例
検索対象パタン
parfait
ビットマスク
a: 01001000 f: 00010000 i: 00000100 p: 10000000 r: 00100000 t: 00000010
クエリ
pafet

受理状態
受理状態を表すビット列
acceptPattern: 00000001
使い方
js
const a = new Asearch("parfait") a.match("pafet", 3)


到達可能なノードを緑色で示していく
各曖昧度での状態が可視化される
p の入力を受け取った直後
初期状態sから一文字認識するだけで、遷移先候補はかなり広がる
若い曖昧度からのε遷移で連鎖的に伝播して着色されていく
各曖昧度で、遷移結果を論理和で重ね合わせる


さらに続ける
pa まで受け取った直後
記号のない黒色矢印は空文字による遷移


状態遷移をコードで表す
若い曖昧度の遷移前の状態を参照するので、曖昧度が大きい方から更新していく
js
i3 = ((i3 & mask) >>> 1) | (i2 >>> 1) | i2 i2 = ((i2 & mask) >>> 1) | (i1 >>> 1) | i1 i1 = ((i1 & mask) >>> 1) | (i0 >>> 1) | i0 i0 = (i0 & mask) >>> 1
最後に、遷移後の状態を参照して算出されるε遷移のシフト演算を行う
こちらは曖昧度が若い方から更新する
js
i1 = i1 | (i0 >>> 1) i2 = i2 | (i1 >>> 1) i3 = i3 | (i2 >>> 1) currentState = [i0, i1, i2, i3]
受理判定
js
// 曖昧度 const ambig = 3 const isAccept = (currentState[ambig] & acceptPattern) !== 0


完全マッチの可能性がなくなった
paf まで受け取った直後
入力文字 f のビットマスク
0001 0000
i0
前: 0010 0000
後: 0000 0000
右への遷移なし
(i0 & mask) >>> 1


曖昧度3で受理されるまでの様子
pafe まで受け取った直後
pafet
曖昧度2でのマッチの可能性がなくなった
曖昧度3で受理された


振り返り
ここまでは、検索時の様々な技術を紹介した
ここからは、検索時に機械的な言い換えやマッチ判定が難しいケースに対処する話
データセット構築時にできることはなんだろうか?


各記事にメタデータとして説明を追加する
ヒットさせたい表現を書き足していくことで、一般的な全文検索を超えられる
短い記述で膨大な表現に展開される記述方法を用意
動詞の活用形の全パターンを展開、読み仮名検索などに自動に対応
くだけた表現を気兼ねなく書ける
記述法の例
helpfeel記法と呼んでいる
? {webpage}の{screenshot}を(撮る|取得する|キャプチャする)方法
これをScrapboxに書く
変数も別途定義できる
Glossary
webpage: (ウェブページ|ウェブサイト) screenshot: (スクリーンショット|スクショ)
展開されるパターン
これらを全てメンテナンスするのは大変だが、上の記法一行だけならできる

動詞のグループを半自動生成
データセットに「乗れる」が登場したとする
これらも自動で追加される
「乗れる」
「乗る」
「乗せる」
「〇〇する」系の動詞の語幹が名詞としても登録される
「調査依頼」に対して、回答「...調査したい」を提示できる
helpdata.json
{ "verbalizedNouns": [ "調査", "引越し", // ... ] }

例1: 可能動詞
パターン①: 五段活用動詞 -> 可能動詞
読む(mu) + れる -> 読め(me)る
パターン②: 可能動詞 -> 五段活用動詞
読め(me)る -> 読む(mu) + れる
他方を導出して、一緒くたに扱えるようにする
仕組み
与えられた動詞からパターンを決定する
元の動詞 (左辺) からペア動詞 (右辺) を導く
ペア動詞を形態素解析エンジンに通し、有効な下一段活用動詞または五段活用動詞であるか確認する

例2: 自動詞と他動詞
〜が「乗る」、〜を「乗せる」
規則性が見当たらないので、見つけ次第手動でプログラムに追加していく
データセットに verbGroups として入っている
helpdata.json
{ "verbGroups": [ ["乗る", "乗せる", "乗れる"] // ... ] //... }
記事の解説立場と検索者の立場のズレを吸収
乗りたい、乗せてもいいか
文法上は厳密には異なる動詞であっても、意味が同じなら同一とみなす
払えますか、支払う方法

まとめ
クライアントサイドでの検索
応答速度を意識した検索タスクの実行方法
結果一覧での表現を検索語の表現に合わせる、重要語のハイライト
高速な曖昧検索
文書拡張の考え方
クエリの変形や関連性だけでは解決できない言い換えへの対応
必要な表現をメタデータとして追加することでヒット率を向上できる