会話版「もしかして」を実現？ プログラムで言い間違いを検知する

こんにちは。
開発チームのワイルド担当、まんだいです。

言い間違いや聞き間違いというのは、会話においてよく起こる事だと思います。
その場の雰囲気や状況にもよりますが、大抵の場合、場を和ませてくれる要素もあったりするので、悪い事ではないと思います（明らかに覚え間違っている場合もありますが）。

今回は、Google検索で出てくる、「もしかして」の実装が可能になる（かも知れない）アルゴリズムを幾つか紹介します。

 

目次

1. レーベンシュタイン距離
2. soundex
3. metaphone
4. その他関連記事

 

レーベンシュタイン距離

まずは、文字と文字の距離を数値化するレーベンシュタイン距離です。

レーベンシュタイン距離 - Wikipediaによると

二つの文字列がどの程度異なっているかを示す距離の一種である。編集距離（へんしゅうきょり、英: edit distance）とも呼ばれる。

と紹介されていて、Wikipediaでも紹介されている、kittenとsittingの距離を見ていきます。

1. kitten
2. sitten # k → sの置換
3. sittin # e → iの置換
4. sitting # gの追加

という3つの工程を経て、kittenからsittingへの変換は可能で、この場合のレーベンシュタイン距離は3になります。
この作業回数を文字と文字の距離と定義して、近似度合いを測ります。

文字の操作には、追加・削除・置換が考えられますが、置換は追加と挿入を同時に行う操作と見なせるので、置換のコストは本来2になるという見方もあります。
この場合のレーベンシュタイン距離は5になります。

何の役に立つのか、という疑問もありますが、読み進めていくとDNAの研究に応用されているようです。
確かにDNAはAGCTの4つの文字の組み合わせで表されるので、雑に言うと、レーベンシュタイン距離はすなわち遺伝的な近さに置き換える事もできます。

このレーベンシュタイン距離ですが、PHPで簡単に求めることができ、専用の標準関数が存在します。

echo levenshtein('kitten', 'sitting');

// 結果は3

echo levenshtein('kitten', 'sitting', 1, 2, 1);    // 置換のコストを2とした場合

// 結果は5

echo levenshtein('山田', '山口');

// 結果は3

 
がーん。マルチバイト文字には対応していないようです。
UTF8環境で実行したので、漢字が3バイトでカウントされています。よって、第二引数以降を省略した場合は、置換もコスト1と数えられるので3バイト変更したと考えられます。
試しに別の文字列をぶっこんで、ちょっと内部の様子を外から伺ってみます。

echo bin2hex('山');    // e5b1b1
echo bin2hex('口');    // e58fa3
echo bin2hex('田');    // e794b0
echo bin2hex('局');    // e79480 「口」と下2桁が違うだけ

echo levenshtein('山田', '山口');
// 結果は3

echo levenshtein('山田', '山局');
// 結果は3

 
マルチバイト文字をバイト単位で見ているわけではなく、マルチバイト文字として認識はしているようですが、最終的に変換した文字数をstrlen辺りでざっくり確認しているという感じのようです。

実装は割と簡単なようで、PythonとPerlの実装が載っているページがあったので、リンクを貼っておきます。

編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー

 

soundex

soundexはレーベンシュタイン距離とは切り口が違う、より言い間違いにリーチしたアルゴリズムです。
特に個人名に対応できるように設計されているようです。

Wikipediaに日本語の記事がないのですが、英語のページはありました。 → Soundex - Wikipedia

soundexは、入力された文字を発音を解析して4文字のsoundexキーという文字列にします。
どんなに長い文字列でも4文字にするあたり、ちょっと乱暴な気もしますが・・・。

こちらもPHPに標準関数が用意されているので、簡単に実行してみたいと思います。
カタカナで書くと同じになる、英単語を幾つか用意してみました。

echo soundex('rock');

// 結果はR200

echo soundex('lock');

// 結果はL200

echo soundex('free');

// 結果はF600

echo soundex('flea');

// 結果はF400

echo soundex('flee');

// 結果はF400

echo soundex('aerosmith');

// 結果はA625

 
戻り値はさっぱり理解できませんが、rockとlockの違いについては、何となくわかりますね。
free、fleaの違いは2文字目だけで、fleaとfleeに関しては完全に同じです。

変換の細かいルールが意外とたくさんあるので、文字列の類似度を測る(2) 発音に着目する｜Colorless Green Ideasに書かれているのを参照していただくとして、soundexとレーベンシュタイン距離を組み合わせると、発音の方面から、「もしかして」機能の実装ができそうです。

soundexはMySQLでもサポートされていて、soundex関数が用意されています。

MySQL :: MySQL 5.6 リファレンスマニュアル :: 12.5 文字列関数 SOUNDEX(str)

MySQLのsoundexは、PHPの出力と少し違っていて、4文字固定ではない事に気をつけなければいけません。

mysql> SELECT SOUNDEX('Quadratically');
        -> 'Q36324'

 
soundex関数は日本語非対応です。
言語仕様上、同じ物差しでは測れないので当然っちゃ当然かも知れませんが。

 

metaphone

metaphoneはLawrence Philips氏が考案したアルゴリズムで、soundexと同じように、発音をベースにmetaphoneキーという文字列を出力するアルゴリズムです。
soundexは、文字を順番に見て発音を見分けていますが、metaphoneは文字の組み合わせと発音が定義されていて、soundexキーより正しいデータが得られるようです。

metaphoneキーは、母音を除いたアルファベットだけで構成されます。
metaphoneキーは「0BFHJKLMNPRSTWXY」の16文字で構成されます。
0はthの音を表すようで、単体のTとHとは区別されているようです。
例外的に、authenticationのように母音で始まる場合のみ、母音が付くというルールがあります。
その他にも、組み合わせによる変換ルールがsoundex以上に多数あり、これがsoundexより正しいデータが得られる理由です。

こちらもPHPにmetaphoneという標準関数がありますのでサンプルを見てみましょう。

echo metaphone('authentication');

// 結果はA0NTKXN

echo metaphone('supercalifragilisticexpialidocious');    // メリー・ポピンズで有名なあれ
// 結果はSPRKLFRJLSTSKSPLTSS

 
発音を文字にするという意味では、発音記号と似た性質ですが、発音記号は正しい発音をするためのもので、metaphoneやsoundexは発音に含まれる音を抽出したような内容なので、metaphoneキーを見ればその単語の発音が分かるわけではありません。

複数の単語のmetaphoneキーを取得し、レーベンシュタイン距離を測れば、soundexよりも精度の高い近似度合いが得られそうです。

metaphone関連の情報は、Lawrence Philips' Metaphone Algorithmこちらにあります（リンク切れが多くメンテされていないので、情報が古い場合があります）。

また、metaphoneのアルゴリズムには、double metaphoneという改良されたバージョンもあって、プライマリーキーとセカンダリキーの2種類を出力するよう、内容が変わったものになっています。
扱う文字列などの基本的なルールは変わらないようですが、中身の実装はかなり変わっているので、metaphoneとdouble metaphoneで結果を比較する事はできなさそうです。

double metaphone関連の情報は、PHP DoubleMetaPhoneにまとまっていて、PHP以外のdouble metaphone実装へのリンクもあります。

double metaphoneはPHPの標準関数にはないので、PECL :: Package :: doublemetaphoneから、PECLで提供されているライブラリを読み込む必要があります。

 

関連

Jazzyというスペルチェックを行うJava APIの説明ページですが、冒頭部分でsoundex、metaphone、レーベンシュタイン距離について解説があります。
soundexが特許を取っていることに驚きです。

Jazzyに勝るものはありません

この辺りの技術を使って、面白い事を研究していた人がおられたので、リンクを貼っておきます。
研究論文ですが、内容は割とフランクで、読みやすいです。

洋楽歌詞からの空耳フレーズ自動生成に向けた一検討

 
以上です。