本当に役立つFAQ検索システムを目指して

2021/3/11

https://gyazo.com/56264d518cb334770c577d7f08824eec https://twitter.com/notainc_jp/status/1368748505016102913

こんばんは

Helpfeelの検索技術の話をします

開発、運用チーム

プロダクトオーナー

daiiz.icon

プロジェクトマネージャー

akix.icon

Webディレクター

テクニカルライター

https://gyazo.com/b68fccefe7ffb47ee08923735793670d/raw

カスタマーサクセス

https://gyazo.com/520ac55862a765e04cc5f42f2dd3364d/raw

エンジニア、デザイナー

予測検索 Helpfeel

https://gyazo.com/88b40ea0bb99879447681cab066824c4

テキパキと高速に検索できている

クエリの表現に合わせて柔軟に結果が提示される

Agenda

いかにして探すか

1. 入力に対して遅延なく検索結果を返す

2. 結果一覧に提示する記事タイトル表現の選び方

3. 効率よく曖昧検索する

ヒット率を高めるデータセットの作り方

4. 効率よく言い換え表現を量産する技術

動画

https://www.youtube.com/watch?v=jEgsKENuXgs

クライアントで快適に検索処理を実行するためには必要不可欠

重いタスクを別のスレッドに移譲して、UIスレッドの負荷を軽減する

postMessage

code:js

// Window

const worker = new Worker('worker.js')

worker.onmessage = event => {

// WebWorkerからの応答を受信

}

worker.postMessage(data)

code:js

// DedicatedWorkerGlobalScope

self.addEventListener('message', event => {

// ここでタスクを処理

// clientに返信

self.postMessage({result: ''})

})

検索頻度の制御

タスクが積まれ過ぎて実行待ち増えすぎないよう注意する

検索頻度の制御に失敗すると？

https://gyazo.com/19b9e62dec9920fad3294b0405d730d9/raw

onInputやonMessageで受けるイベントがじわじわ遅れていく

イベント発火のタイミング

ブラウザ内部のtask queueから取り出されたとき

「文字入力→検索処理→結果の表示」の一連の処理をひとつの塊と考える

検索処理の途中で入力されたクエリを無視する

workerが空いたときに最新のクエリで検索する

つねに一件の検索だけ実行される

不要なタスクの実行を極力避けられる

結果一覧のDOMの描画更新までを見届ける

workerだけでなく、UIスレッドの描画タスクの状況にも気を配る

検索タスクが間引かれる様子

UIスレッド側に、workerに発行するタスクを管理する仕組みを独自に実装した

https://gyazo.com/347ed428f3c348ec7b7e0480aec749ff/raw

Helpfeelでは、一つの回答記事に対して複数の「言い換え表現」が紐付いている

https://gyazo.com/31c558a8c3b70e29eae61119626d8d60

このページに記述するメタデータの例

? 画像間の関連情報を辿って探す

? 芋蔓的に画像を辿る

? 記憶を辿って芋蔓検索する

? 思い出の写真を探す

「記憶」「思い出」「辿る」「探す」などのキーワードでヒットできる

データセット

検索のためにクライアントに送信されるデータ

展開されたすべての言い換え表現が含まれている

code:helpdata.json

{

"faqs": [

{ "pageId": "001", "title": "画像間の関連情報を辿って探す", "verbs": {...} },

{ "pageId": "001", "title": "芋蔓的に画像を辿る", "verbs": {...} },

{ "pageId": "001", "title": "記憶を辿って芋蔓検索する", "verbs": {...} },

// ...

],

// ...

}

この他、動詞、重要キーワードや読み仮名の情報も入っている

どの表現を選ぶかが重要になってくる

ユーザーの用いた検索語をできるだけそのまま反映させたい

動詞を探す

受け取ったクエリが、動詞かそれ以外であるかを字面から判定する

動詞は活用される

クエリ中の活用された動詞を基本形に正規化する

撮りたい → 撮る

撮った → 撮る

撮れない → 撮れる

以降はこの基本形を持つエントリを探せばよい

活用語尾を意識した文字列探索を行わずに済む

ハイライト

ヒット箇所が動詞の場合、語幹だけでなく活用語尾まで着色する

視覚的な安定性があり、瞬時に理解しやすい

https://gyazo.com/117bb1da7bd99973eaa6608abc552ce6/raw

基本形と活用形を全て生成している

活用語尾は規則的に変化するので機械的に処理しやすい

code:helpdata.json

{

"verbs": {

"撮る": [

"撮ら", "撮り", "撮る", "撮れ", "撮ろ", "撮っ"

],

"撮れる": [

"撮れ", "撮れる", "撮れれ", "撮れろ", "撮れよ"

]

},

"verbGroups": [

],

"faqs": [

]

}

基本形に正規化された動詞を持つエントリを絞り込む

同時に活用された表記も取得できる

重要度が高い単語をハイライト

文字入力する度に更新される

https://gyazo.com/e543356f9b0a03e28ff0418acb7104d7

ColoredTextLayer

このdiv要素に、textareaの内容を透明色の文字として表示し、この文字列に対してborder-bottomを与える

線の位置を正確に特定するため、フォントや文字サイズ、折り返し等もそのまま反映させる

code:html

<div className='query-textarea-container'>

<textarea className='query-textarea' />

<ColoredTextLayer text={sentence} hits={hits} />

</div>

code: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から返される

重要度が高い語の推定

動詞に重きをおいて探す

文章全体で保持する結果

これまでの文章でヒットした語と、対象のテキストを渡す

code:js

// hits: textareaで下線ハイライトする語の表層形

const { faqInfos, hits, hitVerbs, hitRareWords, hitBaseForms } = searchBySentence(text, {

prevVerbs: _hitVerbs, // ポイント: 後続の文の解析でも参照する

prevWords: _hitRareWords

})

一文を受け取って検索する関数

動詞を抽出し、回答候補を探す

prevVerbsも含めて、抽出した動詞を出現頻度が低い順にソートする

続いて動詞以外の自立語で探す

工夫

自然文を受け取るので、意味のある動詞が含まれるという仮説

基本的には一つのことについて書かれているはずなので、直前までの内容も重要

データセット構築時に名詞や動詞を希少度が高い順にソートしている

曖昧検索

https://gyazo.com/3637e2b42e0a817893a761a7f3d86ada/raw

正規表現では記述できないような曖昧な表現で検索したい

→ 曖昧度 (編集距離) を許容した文字列マッチを実現したい

うろ覚えな言葉やスペルミス、表記ゆれを吸収できる

ディスクトップ、ハードデスク

Andoid、Gyozo、Scarpbxo

インターフェース、インタフェイス

愚直に文字列比較を繰り返すのは大変

曖昧検索のアルゴリズム

効率の良い手法が存在する

bit-parallel approximate pattern matching

特徴

ビット演算の並列性を利用した文字列探索アルゴリズム

編集距離に基づいた類似文字列の検索を行える

曖昧さ

余計な文字の混入

文字を間違えている

文字が足りない

ビットシフト演算と論理演算だけで高速に実行できる

曖昧検索ライブラリ

文字列マッチ問題は、NDFAで受理されるか？と考える

一文字認識されるたびに次の状態に遷移する

遷移先の選択肢が一意でなくてもよい

この特性を活かして曖昧さを込めた文字列の一致判定を実現できる

最終的に受理状態のノードに到達したらマッチ成功

曖昧度ゼロ (完全一致) の場合の状態遷移機械

https://gyazo.com/84215c4d1e9fbe4dcb2e28285c4c0e4e/raw

パタン「daiiz」を認識する状態遷移機械

曖昧度を持つ文字列マッチをNDFAで表現する

クエリ「taiz」がパタン「daiiz」に曖昧度2でマッチする様子

https://gyazo.com/24f886d170c7a66a6f0d124564b7d903/raw

*: 任意の文字

ε: 空文字

asearchでは、この状態遷移を少ないメモリで実行できる

曖昧性と遷移の対応

余計な文字の混入

https://gyazo.com/fbcf244504a79daea5b9a9611cef1e4d/raw

上に遷移

文字を間違えている

https://gyazo.com/1fd4372e8ce2ee27fec1640dbedec21f/raw

右上に遷移

文字が足りない

daiz

https://gyazo.com/99eafcd50fe6578030c21f697b9797fe/raw

右上に遷移

一致時

横方向に遷移

曖昧度3でマッチする例

検索対象パタン

parfait

code:ビットマスク

a: 01001000

f: 00010000

i: 00000100

p: 10000000

r: 00100000

t: 00000010

クエリ

pafet

受理状態

https://gyazo.com/ed97ce631be3af9be4815b9fc134c37b/raw

code:受理状態を表すビット列

acceptPattern: 00000001

使い方

code:js

const a = new Asearch("parfait")

a.match("pafet", 3)

到達可能なノードを緑色で示していく

各曖昧度での状態が可視化される

https://gyazo.com/3d4a3e3dd6ffa88f9eb7eeb742ef2a3c/thumb/600#.png

初期状態sから一文字認識するだけで、遷移先候補はかなり広がる

若い曖昧度からのε遷移で連鎖的に伝播して着色されていく

https://gyazo.com/f4e0ce16f8a06e244f81b385e58d3260

各曖昧度で、遷移結果を論理和で重ね合わせる

さらに続ける

https://gyazo.com/a9ee3892a40826ed0fe2fb4347273fc7/raw

記号のない黒色矢印は空文字による遷移

https://gyazo.com/33b9cddd36d980d3f1a8d52b89cea153

状態遷移をコードで表す

若い曖昧度の遷移前の状態を参照するので、曖昧度が大きい方から更新していく

code: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

最後に、遷移後の状態を参照して算出されるε遷移のシフト演算を行う

こちらは曖昧度が若い方から更新する

code:js

i1 = i1 | (i0 >>> 1)

i2 = i2 | (i1 >>> 1)

i3 = i3 | (i2 >>> 1)

受理判定

code:js

// 曖昧度

const ambig = 3

完全マッチの可能性がなくなった

https://gyazo.com/5d36b7100fa9faf315d1b983370900e6/raw

0001 0000

i0

右への遷移なし

(i0 & mask) >>> 1

曖昧度3で受理されるまでの様子

https://gyazo.com/ca1b1fb99b103227dc5bfe49438a0f78/raw

pafet

https://gyazo.com/c7f4cc0036c2a5386fe27f0ec4ba960d/raw

曖昧度2でのマッチの可能性がなくなった

曖昧度3で受理された

振り返り

ここまでは、検索時の様々な技術を紹介した

ここからは、検索時に機械的な言い換えやマッチ判定が難しいケースに対処する話

データセット構築時にできることはなんだろうか？

各記事にメタデータとして説明を追加する

ヒットさせたい表現を書き足していくことで、一般的な全文検索を超えられる

短い記述で膨大な表現に展開される記述方法を用意

動詞の活用形の全パターンを展開、読み仮名検索などに自動に対応

くだけた表現を気兼ねなく書ける

記述法の例

? {webpage}の{screenshot}を(撮る|取得する|キャプチャする)方法

これをScrapboxに書く

変数も別途定義できる

code:Glossary

webpage: (ウェブページ|ウェブサイト)

screenshot: (スクリーンショット|スクショ)

展開されるパターン

https://gyazo.com/a7f36841563feee71d136ea0a12ea725 https://regexper.com/#%28%3F%3A%E3%82%A6%E3%82%A7%E3%83%96%E3%83%9A%E3%83%BC%E3%82%B8%7C%E3%82%A6%E3%82%A7%E3%83%96%E3%82%B5%E3%82%A4%E3%83%88%29%E3%81%AE%28%3F%3A%E3%82%B9%E3%82%AF%E3%83%AA%E3%83%BC%E3%83%B3%E3%82%B7%E3%83%A7%E3%83%83%E3%83%88%7C%E3%82%B9%E3%82%AF%E3%82%B7%E3%83%A7%29%E3%82%92%28%3F%3A%E6%92%AE%E3%82%8B%7C%E5%8F%96%E5%BE%97%E3%81%99%E3%82%8B%7C%E3%82%AD%E3%83%A3%E3%83%97%E3%83%81%E3%83%A3%E3%81%99%E3%82%8B%29%E6%96%B9%E6%B3%95

これらを全てメンテナンスするのは大変だが、上の記法一行だけならできる

動詞のグループを半自動生成

データセットに「乗れる」が登場したとする

これらも自動で追加される

「乗れる」

「乗る」

「乗せる」

「〇〇する」系の動詞の語幹が名詞としても登録される

「調査依頼」に対して、回答「...調査したい」を提示できる

code:helpdata.json

{

"verbalizedNouns": [

"調査",

"引越し",

// ...

]

}

例1: 可能動詞

パターン①: 五段活用動詞 -> 可能動詞

読む(mu) + れる -> 読め(me)る

パターン②: 可能動詞 -> 五段活用動詞

読め(me)る -> 読む(mu) + れる

他方を導出して、一緒くたに扱えるようにする

仕組み

与えられた動詞からパターンを決定する

元の動詞 (左辺) からペア動詞 (右辺) を導く

ペア動詞を形態素解析エンジンに通し、有効な下一段活用動詞または五段活用動詞であるか確認する

例2: 自動詞と他動詞

〜が「乗る」、〜を「乗せる」

規則性が見当たらないので、見つけ次第手動でプログラムに追加していく

code:helpdata.json

{

"verbGroups": [

// ...

]

//...

}

記事の解説立場と検索者の立場のズレを吸収

文法上は厳密には異なる動詞であっても、意味が同じなら同一とみなす

まとめ

クライアントサイドでの検索

応答速度を意識した検索タスクの実行方法

結果一覧での表現を検索語の表現に合わせる、重要語のハイライト

高速な曖昧検索

文書拡張の考え方

クエリの変形や関連性だけでは解決できない言い換えへの対応

必要な表現をメタデータとして追加することでヒット率を向上できる