#概要
文字列の完全一致ではなく、編集距離によって求めた文字列の近さを指標とすることで、音声認識を多少間違えても正しい検索結果が表示されやすいキーワード検索プログラムを作りました。
具体例として本稿では、事前に取得したテレビ番組名リストから、特定キーワードを含むものを音声認識で見つけるプログラムを作ります。これができると例えば、下記のような番組名をスマートスピーカに伝えてチャンネルを変更するスキルを作るのに役立ちます。

アレクサに番組名をいうとチャンネルを変えてくれるようにしました pic.twitter.com/IRQkzHG9O4
— しまじろう@はかせちゃれんじ (@shimajiroxyz) April 21, 2020

なお音声認識誤りを編集距離でカバーする発想自体は特に新規ではありません（参考）。
本稿は具体的な実装例の紹介という位置づけです。

#背景
音声認識APIの登場や、スマートスピーカの普及に伴い、一般ユーザでも音声認識結果に応じた分岐処理を伴うプログラムを書く機会が増加しています。
キーボード入力などにくらべ、音声入力では認識誤りが生じやすいため、認識誤りが生じることを想定したシステムを作ることが重要です。
例えばたくさんの文字列のリストから特定単語と完全一致する部分を含むものだけを取得するようなキーワードマッチングのタスクでは、音声認識を１文字でも間違えてしまうと、とたんに正しい結果を表示できなくなります。

このような脆弱さは文字列の完全一致のような「きつい」判定基準を採用している場合に生じます。
キーボード入力よりもミスが生じやすい音声認識を前提としたシステムでは１文字か２文字くらいは間違ってても大丈夫な「ゆるい」判定基準を設けることで音声認識誤りに頑健なシステムを作ることができると期待されます。

そこで本稿では、編集距離を指標とすることで、音声認識を多少間違えても正しい検索結果が表示されやすいキーワード検索プログラムを作りました。編集距離は音声認識誤りを訂正するために用いられることがあり（参考）、本稿の実装でも有用な指標になりうると考えました。
具体例として本稿では、事前に取得した番組タイトルリストから、特定キーワードを含むものを音声認識で見つけるプログラムを作ります。
#編集距離
編集距離は２つの文字列の近さ（類似度）を表す指標の一つです。
編集距離はある文字列を別の文字列に変換するときに必要な編集操作の最小回数として計算されます。編集操作とは「置換」「挿入」「削除」のいずれかを指します。
感覚的には、ある文字列を１文字ずつ変化させて別の文字列にするときにどのくらい手間がかかるかという指標で、編集距離が小さいほど、文字列の類似度が高いと判断します。
例えば「アキバ」と「マキバ」は編集距離が１、「アキバ」と「ワオン」は編集距離が３です。

文字列の近さの数値化には色々な方法があるので、より詳しく知りたい方は下記のページなどを参考にしてください。
【技術解説】似ている文字列がわかる！レーベンシュタイン距離とジャロ・ウィンクラー距離の計算方法とは
#音声認識結果を利用したテレビ番組検索
具体例があったほうが説明しやすいので、テレビ番組検索を例にします。
今回は番組リストと検索ワードが与えられたとき、検索ワードが含まれている可能性の高い番組名を取得するプログラムを作ります。

#準備
##環境
macOS Catalina 10.15.4
python3.8.0
##インストール

editdistance
- 編集距離の計算に使います。pip install editdistanceでインストールできます。
MeCab
- 編集距離を計算するための前処理（主にはカタカナ読みへの変換）に利用します。インストール方法は各所で紹介されているのでここでは省略します。

##番組表の用意
検索先にする番組タイトルのリストを用意します。
今回は練習なので、適当に用意したリストを使います。
本稿の末尾に「付録：練習用番組リスト」を載せておきますので、コピーして、program.csvという名前で保存してください。

##ファイル構成
検索を行うソースコードであるsearch.pyと番組リストprogram.csvを同じ階層に配置してください。
program.csvは番組タイトルが１行につき１つ書かれている形式です。

- search.py
- program.csv

#コード
コードの処理を簡単に述べていきます。
大まかには、番組タイトルリストと検索ワードをすべてカナ表記に直した上で、編集距離を計算し、検索ワードが含まれている可能性の高い、番組タイトルを返す、という流れです。
コード全体はこの次の節に記載しています。
##インポートと変数の宣言
必要なライブラリと各種変数をインポート、宣言します。

search.py

import MeCab
import editdistance as ed

#番組表のファイルパス
program_file_path = 'program.csv'

#MeCabのパーサを繰り返し使うので先に宣言しておく
m = MeCab.Tagger()

##編集距離を計算する前処理
編集距離を適切に計算するために、漢字仮名交じり文をカナ表記に変換する関数を作ります。
検索ワードと番組名を両方とも__カナ表記に統一することで表記ゆれが編集距離に影響することを避ける__ことができます。
同じ理由で発音に関係ない記号も邪魔なので、除きます。
これらの処理をMeCabの解析結果にもとづきおこなう関数を作ります。
このコードではMeCabのデフォルト辞書を用いていますが、mecab-ipadic-neologdを用いたほうが読みがなの検出精度は上がると思います。
重要なことは漢字仮名交じり文から読みがなを取得することと記号を削除することなので、これらの処理ができればMeCabを使う必要は必ずしもありません。

search.py

#MeCabを使って漢字仮名交じり文から読みを取得する関数
def getYomi(text):
    #MeCabの解析結果を取得
    #1行にひとつの形態素が書かれている
    parse_result = m.parse(text).splitlines()
    #読みの部分を取り出して、変数に追加していく。
    #ついでに記号は読み方に関係しない（と想定される場合が多い）ので除く
    yomi = ''
    for elem in parse_result:
        #タブが含まれていない行は無視する
        if '\t' not in elem: continue 
        #MeCabの解析結果の各行は「入力形態素（surface）+ タブ +付加情報（info）」の形式
        #付加情報は品詞、語幹、原型、読みなどの情報がカンマ区切りになっている
        surface = elem.split('\t')[0]
        info = elem.split('\t')[1].split(',')
        #infoの情報が少なすぎる行は処理しない
        if len(info) < 3: continue

        #infoから品詞と読みを取得
        pos = info[0] #infoの最初の要素がメインの品詞
        y = info[-2] #infoの最後から２番めの要素が読み（カナ）
        
        #発音しない形態素については処理しない
        #品詞が「記号」の場合、処理しない
        if pos == '記号': continue
        #'・'の品詞は普通「記号」だが、数字の後ろに'・'が来ると「名詞・数」となって除けないので、例外処理
        if surface == '・': continue
        #MeCabのデフォルト辞書では未知語をサ変接続の名詞とするため、一部の記号もそのように解析されてしまう
        #そこで「名詞」かつ「サ変接続」かつ「読みが未知（*）」のときには記号の可能性が高いと判断して処理しない
        if pos == '名詞' and info[1] == 'サ変接続' and y == '*': continue
        
        #未知語は読みが'*'となる。このときはsurfaceを読みとして採用する。
        if y == '*': y = surface
        #それまでの読みに新たな読みを足す
        yomi += y
    return yomi

##検索
キーワードが引数として与えられたとき、そのワードを含んでいると考えられる番組タイトルの候補を返す関数を記述しています。

search.py

def searchKeyword(word):
    #program_file_listの情報を読みに変換して取得
    titles, kana_titles = [],[]
    with open(program_file_path) as f:
        titles = f.read().splitlines()
        kana_titles = [getYomi(v) for v in titles]
    #検索対象の読みを取得
    kana_word = getYomi(word)
    
    #各kana_titleと検索対象の文字列長差分を調整した編集距離を取得
    eds = []
    for kana_title in kana_titles:
        #編集距離を計算
        d = ed.eval(kana_title,kana_word)
        #番組タイトルのほうが長い場合にはその差を編集距離から減じる
        if len(kana_title)>len(kana_word):
            d -= (len(kana_title)-len(kana_word))
        eds.append(d)
    #編集距離の最小値を取得
    min_ed = min(eds)
    #編集距離が最小値の番組タイトルを取得
    candidate_titles = [t for t,e in zip(titles,eds) if e == min_ed]
    return candidate_titles

for文の中にある下記の部分が、音声認識誤りに頑健なキーワード検索を実現している部分です。

        #編集距離を計算
        d = ed.eval(kana_title,kana_word)
        #番組タイトルのほうが長い場合にはその差を編集距離から減じる
        if len(kana_title)>len(kana_word):
            d -= (len(kana_title)-len(kana_word))

２行目で番組タイトルのカナ表記kana_titleと検索ワードのカナ表記kana_wordの編集距離を計算しています。
ただしこれだけだと、「検索ワードを含む文字列」を検索するための指標としては適していません。ユーザが番組タイトルの一部しか発話しなかった場合に、検索ワードと番組タイトルの文字列長の差だけ余分な編集操作が生じ、編集距離が大きくなるからです。
この影響を廃城するための処理が４行目と５行目です。番組タイトルのカナ表記が検索ワードのカナ表記よりも長かった場合には、文字数の差だけ編集距離を小さく補正しています。
##検索機能の改善点
検索機能には簡単に思いつく範囲で3つ改善の余地があります。
今回はシンプルに実装することを優先しましたが、もし精度が不十分と感じられる場合には、これらの改善を検討する余地があります。

１つはそれは、検索ワードの文字がバラバラに長い番組タイトル中にたまたま含まれていた場合に補正後の編集距離の評価が高くなってしまうのを避けることです。
例えば報道番組を見たくて「報道（ホウドウ）」を検索ワードにしたとき、「報道ステーション（ホウドウステーション）」のような番組タイトルはもちろん検出できますが、「本格的超ド級戦艦（__ホ__ンカクテキチョ__ウド__キュ__ウ__センカン）」のように報道という言葉自体は含まれていないのに「ホ」「ウ」「ド」「ウ」がたまたまバラけて登場した単語も同様に検出してしまいます。これを解決するには、番組タイトルのN-gramや各形態素と検索ワードの編集距離を指標に入れるという方法が考えられます。
ただしその分、コードが複雑化したり、計算時間が長くなる可能性があります。折衷案としては、検索ワードが短いほどこうした問題は生じやすいと考えられるので、検索ワード文字数がしきい値以下のときだけ、N-gramとの比較を実施する、などのようにするのはありかもしれません。

２つめは音素間の発音の近さを考慮することです。
編集距離は文字の異同しか判断しません。子音だけが異なる「あがさ」と「かばた」でも、子音も母音も全く異なる「あがさ」と「ぽえむ」でも、どちらも編集距離は３です。
一方で、音声認識で誤って認識された単語は、正しい単語と母音だけは等しかったり、子音だけは等しかったりといったことが多くなると期待されます。したがって、入力インターフェースが音声認識結果である場合には、母音や子音が一致していた場合には編集距離を小さくするような補正をかけることで、検索の精度を上げられる可能性があります。

3つめは英単語の変換です。
MeCabのデフォルト辞書だと英単語が充実しておらず、それらについては読みがなに変換できずアルファベットのままになってしまい、検索がうまくできない場合があることが予想されます。
例えば"news"という単語はそのままになってしまうため、検索用語が「ニュース」だとこれらを検索できません。
解決策としては、MeCabの辞書をカスタマイズする、英単語と発音カナ表記の対応辞書を別途用意してそれを参照させる、ローマ字読みさせるなどが考えられます。
#コード全体
コード全体は下記になります。

search.py

import MeCab
import editdistance as ed

#番組表のファイルパス
program_file_path = 'program.csv'

#MeCabのパーサを繰り返し使うので先に宣言しておく
m = MeCab.Tagger()

#MeCabを使って漢字仮名交じり文から読みを取得する関数
def getYomi(text):
    #MeCabの解析結果を取得
    #1行にひとつの形態素が書かれている
    parse_result = m.parse(text).splitlines()
    #読みの部分を取り出して、変数に追加していく。
    #ついでに記号は読み方に関係しない（と想定される場合が多い）ので除く
    yomi = ''
    for elem in parse_result:
        #タブが含まれていない行は無視する
        if '\t' not in elem: continue 
        #MeCabの解析結果の各行は「入力形態素（surface）+ タブ +付加情報（info）」の形式
        #付加情報は品詞、語幹、原型、読みなどの情報がカンマ区切りになっている
        surface = elem.split('\t')[0]
        info = elem.split('\t')[1].split(',')
        #infoの情報が少なすぎる行は処理しない
        if len(info) < 3: continue

        #infoから品詞と読みを取得
        pos = info[0] #infoの最初の要素がメインの品詞
        y = info[-2] #infoの最後から２番めの要素が読み（カナ）
        
        #発音しない形態素については処理しない
        #品詞が「記号」の場合、処理しない
        if pos == '記号': continue
        #'・'の品詞は普通「記号」だが、数字の後ろに'・'が来ると「名詞・数」となって除けないので、例外処理
        if surface == '・': continue
        #MeCabのデフォルト辞書では未知語をサ変接続の名詞とするため、一部の記号もそのように解析されてしまう
        #そこで「名詞」かつ「サ変接続」かつ「読みが未知（*）」のときには記号の可能性が高いと判断して処理しない
        if pos == '名詞' and info[1] == 'サ変接続' and y == '*': continue
        
        #未知語は読みが'*'となる。このときはsurfaceを読みとして採用する。
        if y == '*': y = surface
        #それまでの読みに新たな読みを足す
        yomi += y
    return yomi

def searchKeyword(word):
    #program_file_listの情報を読みに変換して取得
    titles, kana_titles = [],[]
    with open(program_file_path) as f:
        titles = f.read().splitlines()
        kana_titles = [getYomi(v) for v in titles]
    #検索対象の読みを取得
    kana_word = getYomi(word)
    
    #各kana_titleと検索対象の文字列長差分を調整した編集距離を取得
    eds = []
    for kana_title in kana_titles:
        #編集距離を計算
        d = ed.eval(kana_title,kana_word)
        #番組タイトルのほうが長い場合にはその差を編集距離から減じる
        if len(kana_title)>len(kana_word):
            d -= (len(kana_title)-len(kana_word))
        eds.append(d)
    #編集距離の最小値を取得
    min_ed = min(eds)
    #編集距離が最小値の番組タイトルを取得
    candidate_titles = [t for t,e in zip(titles,eds) if e == min_ed]
    return candidate_titles

if __name__ == '__main__':
    keyword = 'ブラマヨ'
    res = searchKeyword(keyword)
    print('keyword:',keyword)
    print('\n'.join(res))
    print('')
    
    keyword = 'ガールズブラスト'
    res = searchKeyword(keyword)
    print('keyword:',keyword)
    print('\n'.join(res))
    print('')

    keyword = '報道'
    res = searchKeyword(keyword)
    print('keyword:',keyword)
    print('\n'.join(res))
    print('')

program.csvに「付録：練習用番組リスト」の内容を用いた場合には、下記のような出力が得られれば正しく動いています。「ブラマヨ」や「ガールズブラスト」のように完全一致しない検索ワードでも正しく検出できています。
一方で「報道」では、前述したような「検索ワードに含まれる文字がバラけて登場する番組タイトルも検出してしまう」問題が生じています。実際に使ってみて、あまりに頻発するようであれば、改善を検討するのが良いかと思います。

$ python search.py
keyword: ブラマヨ
ウラマヨ!【貴重映像!巨大(秘)水族館オープン裏側&神戸どうぶつ王国が人気のワケ】
キャラとおたまじゃくし島（3）「ワケありキャラにご用心　の巻」

keyword: ガールズブラスト
ガールズクラフト番外編「Tシャツをリメイク！縫わずに作るお気に入りマスク」

keyword: 報道
ウラマヨ!【貴重映像!巨大(秘)水族館オープン裏側&神戸どうぶつ王国が人気のワケ】
ダーウィンが来た！選「東京多摩川で発見！謎の動物密集地帯」
土曜はダメよ！笑って元気に95分SP!小枝不動産2本立て&赤の他人は誰?
「君の名も。」～人生激変!?同姓同名ストーリー～【MC:博多華丸&山里亮太】
今夜7時放送　芸能人が本気で考えた!ドッキリGPスペシャルを熱弁!
こやぶるSPORTS【五輪メダル候補のアスリートと生中継&小籔がお悩み解決!】

#終わりに
音声認識を用いたキーワード検索システムなどに利用することを想定して、編集距離を用いて音声認識誤りがあっても頑健にマッチングできる検索アルゴリズムを書きました。結果、検索ワードに１文字程度の誤りがある場合でも、正しい検索結果を得ることができました。一方で、特に検索ワードが短い場合には編集距離という指標の特性上、関係のないものがヒットしてしまうなど改善の余地もありました。
何を重点的に改善するべきかは、アプリケーションとして実際に使っていきながら考えていければと思っています。
以下は付録です。
ここまでお読みいただきありがとうございました。

#付録：練習用番組リスト
2020年4月25日の番組表から適当に抜粋した番組タイトルを１行につき１つ記述したものです。
参考：動的に読み込まれるテレビ番組表をスクレイピング【Python】【Selenium】

program.csv

こころの時代～宗教・人生～　それでも生きる～旧約聖書・コヘレトの言葉（1）
サンテレビニュース
よしもと新喜劇【～傑作選！川畑座長プレゼンツ～★「白熱!?夫婦１グランプリ」】
中居正広のニュースな会
ウラマヨ!【貴重映像!巨大(秘)水族館オープン裏側&神戸どうぶつ王国が人気のワケ】
嵐にしやがれ【中川家の爆笑貧乏話＆櫻井が特撮ヒーローに変身！】
麒麟（きりん）がくる（14）「聖徳寺の会見」
ええじゃないか。　ふれあいたっぷり旅
警視庁・捜査一課長　スペシャルII
土曜スタジオパーク『エール』特集▽ゲスト　森山直太朗
東大王★わずか２連勝で敗れた新生東大王★チームに救世主！２か月ぶりに鈴木光が復帰
モモコのOH!ソレ!み～よ!【野球古田敦也、福山雅治と意外な関係】
やすとも×中川家の旅はノープラン2019【春の福岡編】
第49回NHK講談大会
テレビショッピング
おかべろ【今田耕司、芸歴35年!吉本を語る】
名曲アルバム「ゴンドラをこぐ女」リスト作曲
キャラとおたまじゃくし島（3）「ワケありキャラにご用心　の巻」
サウンドコンポ
グータンヌーボ2
ニュース
うまDOKI
ジョブチューン★『大戸屋×超一流和食料理人』＆『風水師が自宅をジャッジ』★
ダーウィンが来た！選「東京多摩川で発見！謎の動物密集地帯」
土曜はダメよ！笑って元気に95分SP!小枝不動産2本立て&赤の他人は誰?
「君の名も。」～人生激変!?同姓同名ストーリー～【MC:博多華丸&山里亮太】
フジサンケイレディスクラシック特別編ライブ!
プレマップ
みんなで筋肉体操　今こそ体を動かそう（4）「シーズン2　スクワット＆背筋」
先人たちの底力　知恵泉「ヒールの言い分！時代劇定番の大悪人　松永久秀」
10分でわかる！麒麟（きりん）がくる「さよなら、道三編」
ライフライン情報（関西）
いいね!テレビショッピング
NHKスペシャル「緊急事態宣言　いま何が起きているのか」
Nコン2020　1人でできる！合唱レッスン
今夜7時放送　芸能人が本気で考えた!ドッキリGPスペシャルを熱弁!
ガールズクラフト番外編「Tシャツをリメイク！縫わずに作るお気に入りマスク」
テレビショッピング
クレヨンしんちゃん　【家の中で楽しむゾスペシャル!!】
もしもツアーズ
アニメ　きみのおうちへ（LOST　AND　FOUND）
おかあさんといっしょ　土曜日
住人十色【中!? 外!? ど真ん中に大きな土間のある家】
ドラえもん　【気球で世界一周!?】【大ピンチ!スネ夫の答案】
こやぶるSPORTS【五輪メダル候補のアスリートと生中継&小籔がお悩み解決!】
news every.サタデー
新型コロナウイルス　医師が伝えたいこと「リウマチの方へ」
プロフェッショナル「緊急企画！プロのおうちごはん」
パッコロリン「にじがいっぱい」
アニメ　ねこねこ日本史「いろいろ試して百二十年、江戸三大改革！」
いいね!テニス
サンテレビニュース