nkf&KAKASIと編集距離で"それっぽい"見出し語を検索する

ご挨拶

バイトルなどでおなじみのディップ株式会社に新卒で入社しました @raitehu です．

この記事は何？

今年の春にわたしたち新卒3人に与えられた研修課題は「いい感じに社内用語を検索できるシステム」を作ることでした．
そのシステムの内部で実装した表記ゆれ・誤字脱字があっても"それっぽい"言葉を検索する機能についてご紹介します．

作ったもの

1. ユーザがSlackで「ask hoge」と発言する
2. あらかじめ登録してある見出し語と解説をSlack botが発言する(部分一致)
3. もし2.で一致する語が見つからなかった場合は"それっぽい"語を3つほどサジェスチョンする

というアプリです．
実際にはタグ機能や登録・編集・削除といった機能もありますが，
本記事では3.の"それっぽい"語を探す部分をピックアップしてお話します．

表記ゆれ・誤字脱字への対応

完全一致・部分一致では検索できないものが多すぎる

たとえばQiitaという見出し語が登録されていたとして，
qiita，キータという検索ワードもヒットさせたい...どうすれば...
かといってヒットさせたい全ての単語を一つの解説文に登録させなければいけないのも微妙ですよね．

STEP1 大文字・小文字・半角・全角の差異を統一する

Qiita，qiita，Ｑｉｉｔａ，ｑｉｉｔａ，きーた，キータ，ｷｰﾀといった表記ゆれをできるだけ統一して検索する必要がありそうです．
そのためにタイトルにもあるnkf(*1)とKAKASIを利用しました．

1-1 英数字の標準化

nkfによって英数字は半角小文字を標準として統一しておきます．
これは以下のコードで実現できます．

require 'nkf'

def half_width_word(word)
  NKF.nkf("-m0Z1 -W -w", word).downcase
end

これによって，Qiita，qiita，Ｑｉｉｔａ，ｑｉｉｔａは[qiita]に統一できます．

1-2 日本語の標準化

一方できーた，キータ，ｷｰﾀといった日本語も統一しておきたいですね．
欲を言うと[qiita]を検索するメソッドと同じメソッドで検索を行いたいです．
そこで日本語->ローマ字変換プログラムであるKAKASI(*2)を利用しました．

きーた，キータ，ｷｰﾀはnkfによって全角に直し，KAKASIによって半角英数字小文字化します．
上記のコードnkf_sample.rbにKAKASIも足したものが次になります．

require 'kakasi'
require 'nkf'

def generate_romaji(word)
  Kakasi.kakasi('-Ja -Ha -Ka', NKF.nkf("-m0Z1 -W -w", word)).downcase
end

これによって，きーた，キータ，ｷｰﾀは[ki-ta]に統一されました．
このようにして登録段階でフリガナ(実際には英数字)を生成し，見出し語・解説と共にフリガナをDBに登録しておきます．
これで検索段階でも検索ワードのフリガナを生成してフリガナどうしで近いものを探せば見つけられそうだと思いませんか？
(ちなみにKAKASIは独自の辞書を内部にもっているため，漢字も無理やりローマ字に変換されます)

STEP2 "それっぽさ"を測る

2-1 文字列の距離

ここでいう"それっぽさ"とは語句の意味の近さではなくて，文字列の近さ＝編集距離です．
例を出すと，
[ラーメンと中華そば]，[ごはんとライス]は意味的な近さはありますが，文字列的にはまったく近くなく，
[ラーメンとソーメン]，[ごはんとごばん(碁盤)]は意味的には全く近くないですが，文字列的にはかなり近いです．
雰囲気はつかめましたでしょうか？

ラーメン<->ソーメンはラとソを一文字変えるだけで変換可能，
ごはん<->ごばんははとばを一文字変えるだけで変換可能です．
編集操作として追加，編集，削除を考えた文字列同士の距離をレーベンシュタイン距離というそうで，
本サービスもレーベンシュタイン距離を文字列の"それっぽさ"の指標としました．
実装は動的計画法(DP)を用いた，シンプルなものにしました．
(もっと効率的な導出法もあるみたいです(*3))

def calc_levenshtein_distance(word_1, word_2)
  n = word_1.length
  m = word_2.length
  dp_table = Array.new(n + 1){ Array.new(m + 1, 0) }

  (0...n+1).each do |i|
    dp_table[i][0] = i
  end
  (0...m+1).each do |j|
    dp_table[0][j] = j
  end

  (1...n + 1).each do |i|
    (1...m + 1).each do |j|
      word_1[i - 1] == word_2[j - 1] ? cost = 0 : cost = 1
      surrounding_cells = [
                            (dp_table[i - 1][j] + 1),
                            (dp_table[i][j - 1] + 1),
                            (dp_table[i - 1][j - 1] + cost)
                          ]
      dp_table[i][j] = surrounding_cells.min
    end
  end
  dp_table[n][m]
end

これに2つのフリガナを入れてあげることで，その2つのフリガナ間の編集距離が分かります．
たとえば[qiita]と[ki-ta]の距離はqとk，iと-の2文字を入れ替えれば変換可能ですので距離2となります．

2-2 文字列の距離を標準化する

順調そうですが，ここでの問題が1つ．
1万文字がんばって打った中で1文字だけの打ち間違いと2文字打った中での1文字の打ち間違いが同じレベルのミスとみなされてしまうわけです．
割合でいえば0.01%のミスと50%のミスが同等，これはちょっと感覚とズレてますね．
そこで標準化として，2つの文字列のうち長い方の長さで割ってあげるという1工夫をしておきます．

def calc_normalized_levenshtein_distance(word_1, word_2)
  longest_word_length = [ word_1.length, word_2.length] .max
  calc_levenshtein_distance(word_1, word_2).to_f / longest_word_length
end

STEP3 すべての見出し語のフリガナ中，距離最小のものを探す

もうあと一息です．
検索ワードとすべての見出し語の距離が出せるので，距離が小さい順に並べれば"それっぽい"ものを好きな数だけ抽出できます．
以下のサンプルでは一つの解説文に対して複数の見出し語が存在する．
つまり，HeadWordモデル(見出し語)はArticleモデル(解説文)と1対多の関係です．
([Qiita]の解説文に対して見出し語が[qiita],[キータ]など複数いれたかったので...)

なので同一のarticle_idに紐づいた見出し語が複数の編集距離をもちますが，
同一の解説文をいくつも出しても意味がないので複数の見出し語をもつものについては最小のものを採用しています．

また，閾値を設定してあまりにかけ離れた言葉を除外しています．
例では0.5を閾値にしているため，[qiita]に対して
[qita(0.2)],[kita(0.4)],[ki-ta(0.4)],[kiita(0.2)]などはヒットしますが，
[qiiiiiiiita(0.55)],[qixxx(0.6)]などは除外されます．

def search_tolerant(search_word)
  # 検索ワードをローマ字化する
  search_word_romaji = generate_romaji(search_word)
  # head_wordsはid, 見出し語(headword), フリガナ(romaji), article_id(解説文のid)をもつ
  head_words = HeadWord.all
  # 何も登録されていないときは空配列を返す
  return [] if head_words.blank?

  # distance_recirds = {article_id, 編集距離(float型)}のハッシュが格納される配列、格納順序はhead_wordsのid昇順
  # 全見出し語のromajiと検索ワードのフリガナの標準レーベンシュタイン距離を求めていく
  distance_records = []
  head_words.each do |head_word|
    calculated_distance = calc_normalized_levenshtein_distance(head_word.romaji, search_word_romaji)
    distance_records.push({
                            id: head_word.article_id, 
                            distance: calculated_distance
                          })
  end

  # 同一article_idの中で最小の編集距離のものだけに抽出する
  # 閾値を[0.5]とし，これをこえる距離のもの＝半分以上間違ってるものは除外する
  # 結果的に空っぽの配列が帰ってくることもある
  results = distance_records.group_by{ |record| record[:id] }.map do |_, values|
    minimum = values.map{|value| value[:distance]}.min
    {:id => values[0][:id], :distance => minimum} if minimum <= 0.5
  end

  # 閾値を超えるものはnilで記録されるので配列中のnilを消す
  results.compact!

  # 編集距離順にならべかえる
  results.sort_by! { |result| result[:distance] }

  # article_idだけのint配列で返す
  results.map{|result| result[:id]}
end

さいごに

正直なところ社内用語検索が目的なので，検索対象が多くない前提で作っています．
そのため検索速度面では改善の余地がかなりあると思うのでゆくゆくはそのあたりを効率化できたらと思っています．

*1 【 nkf 】コマンド――文字コードと改行コードを変換する
*2 Ruby on Railsで漢字/ひらがな/カタカナをローマ字に変換したい
*3 編集距離（レーベンシュタイン距離）を理解し、実装する