発音の類似度の指標としての編集距離を計算する【python】

#概要
日本語文同士の発音類似度として編集距離を用いる場合に注意したことをまとめました。
またカナ、母音、子音の編集距離を求めるコード例を示しました。
#背景
ダジャレや空耳などの自動生成をするときに文章や単語間の発音類似度を求めたくなることがあります。このときに編集距離を使うことが思いつきます。
編集距離は文字列の類似度の指標として使われる指標であり、ある文字列を１文字ずつ編集（挿入、削除、置換）して別の文字列にするために必要な最小編集回数と定義されます。
日本語ではカナ表記と発音が原則１対１対応するので、カナ表記の編集距離を求めれば、発音がどの程度近いかを知ることができます。
ただし拗音、長音については扱いを気をつける必要があります。具体的には以下の処理が必要です。

* 拗音（シャなど）は発音としては１拍のため、２単位ではなく１単位として扱う。
* 長音（伸ばし棒）は、直前のカナによって（同じ文字でも）発音が異なるので、対応するカナに変換してから編集距離を求める。

また、発音の類似度ということであれば、母音や子音だけに注目した指標を求めたくなることもありそうです。

以上の背景を踏まえ、以下の機能を実装することを目指します。

* カナ文字列をモウラの単位に分割する
* 長音を実際の発音に対応する母音に変換する
* カナ文字列を対応する母音の文字列に変換する
* カナ文字列を対応する子音の文字列に変換する

#環境
macOS Catalina 10.15.7
python 3.8.0
#インストール
編集距離を求めるライブラリをインストールしておきます。

```
pip install editdistance
```
#入力
入力は以下の条件を満たす一意に発音可能なカタカナ文字列とします。

* カタカナのみの文字列である
* 長音（伸ばし棒）や小さいカナで始まるような文字列や、一般的な発音の定義されていない拗音の組み合わせを含まない
* 助詞の「ハ」「ヘ」は実際の発音の音（「ワ」「エ」）に直されている

#前処理機能の実装
##カナ文字列をモウラの単位に分割する

上記前提が満たされた入力文字列をモウラの単位に分割する関数を作ります。

参考：[日本語（カタカナ）をモーラ単位で分かち書き【Python】](https://qiita.com/shimajiroxyz/items/a133d990df2bc3affc12)

```Python
import re

#各条件を正規表現で表す
c1 = '[ウクスツヌフムユルグズヅブプヴ][ヮァィェォ]' #ウ段＋「ヮ/ァ/ィ/ェ/ォ」
c2 = '[イキシシニヒミリギジヂビピ][ャュェョ]' #イ段（「イ」を除く）＋「ャ/ュ/ェ/ョ」
c3 = '[テデ][ャィュョ]' #「テ/デ」＋「ャ/ィ/ュ/ョ」
c4 = '[ァ-ヴー]' #カタカナ１文字（長音含む）

cond = '('+c1+'|'+c2+'|'+c3+'|'+c4+')'
re_mora = re.compile(cond)

#カタカナ文字列をモウラ単位に分割したリストを返す
def mora_wakachi(kana_text):
    return re_mora.findall(kana_text)
```

##長音を実際の発音に対応する母音に変換する
上記でモウラ単位に分割した文字列のうち、長音（伸ばし棒）を発音に対応する母音に変換する関数を作ります。
以下のルールで変換します。

* 直前の要素がア段/イ段/ウ段/エ段/オ段のとき長音をア/イ/ウ/エ/オにする
* 直前の要素が母音を持たないカナ（ッ/ン）のとき、のとき、長音を直前の要素と同じにする
* それ以外のときは変換しない（入力の前提が満たされていれば、「それ以外」という状況は起こらないはずではあります）

まず直前の要素の「段」を判定するために、モウラ１単位を母音に変換する関数を作っておきます。
そして、その関数を使って長音を母音に変換する関数を作ります。

```Python
#受け取ったカナ１単位を母音に変換して返す
#入力はモウラ１単位に相当するカナ文字列（長さ１または２）
def char2vowel(text):
  t = text[-1] #母音に変換するには最後の１文字を見れば良い
  if t in "アカサタナハマヤラワガザダバパァャヮ":
    return "ア"
  elif t in "イキシチニヒミリギジヂビピィ":
    return "イ"
  elif t in "ウクスツヌフムユルグズヅブプゥュヴ":
    return "ウ"
  elif t in "エケセテネヘメレゲゼデベペェ":
    return "エ"
  elif t in "オコソトノホモヨロヲゴゾドボポォョ":
    return "オ"
  elif t == "ン":
    return "ン"
  elif t == "ッ":
    return "ッ"
  else:
    print("no match")
    return text

#入力はモウラの単位で分割されたカナのリスト
def bar2vowel(kana_list):
  output = []
  output.append(kana_list[0])
  #最初に長音がくることは想定しないので、２番めの要素からループを始める
  for i,v in enumerate(kana_list[1:]):
    if v == "ー":
      kana = char2vowel(output[i])#長音が連続した場合に対応するために念の為、outputから直前の要素を取得する
    else:
      kana = v
    output.append(kana)
  return output
```
##カナ文字列を対応する母音の文字列に変換する
カナ文字列を対応する母音の文字列に変換する関数を作ります。
入力はモウラの単位で分割されたカナのリストです。ただし、長音は母音に変換済みとします。
出力における母音はア行のカナで表すこととします。
つまり

* 入力：["コ","ン","ニ","チ","ワ"]
* 出力：["オ","ン","イ","イ","ア"]
のような変換を目指します。
やることは`char2vowel`関数を使って、機械的に置き換えるだけです。

```Python
def kana2vowel(kana_list):
  output = []
  for v in kana_list:
    kana = char2vowel(v)
    output.append(kana)
  return output
```
##カナ文字列を対応する子音の文字列に変換する
カナ文字列を対応する子音の文字列に変換する関数を作ります。
入力はモウラの単位で分割されたカナのリストです。ただし、長音は母音に変換済みとします。
出力における子音は対応するアルファベットで表すこととします。
つまり

* 入力：["コ","ン","ニ","チ","ワ"]
* 出力：["k","N","n","t","a"]
のような変換を目指します。

子音への変換ルールは下記表に基づくこととします。

|子音  |カナ  |
|---|---|
|a  |ア行、ワ行、ヤ行  |
|k  |カ行、キャ行、クァ行  |
|s  |サ行、シャ行、スァ行  |
|t  |タ行、テャ行、チャ行、ツァ行 |
|n  |ナ行、ニャ行、ヌァ行 |
|h  |ハ行、ファ行、ヒャ行 |
|m  |マ行、ミャ行、ムァ行 |
|y  |該当なし (子音aに統合） |
|r  |ラ行、リャ行、ルァ行 |
|w  |該当なし（子音aに統合）  |
|g  |ガ行、ギャ行、グァ行 |
|z  |ザ行、ジャ行、ヂャ行、ズァ行、ヅァ行 |
|d  |ダ行、デャ行 |
|b  |バ行、ヴァ行、ビャ行、ブァ行 |
|p  |パ行、ピャ行、プァ行 |
|q  |ッ  |
|N  |ン  |
|ky  |該当なし（子音kに統合） |
|sh  |該当なし(子音sに統合） |
|ch  |該当なし（子音tに統合）  |
|ny  |該当なし(子音nに統合) |
|hy  |該当なし(子音hに統合) |
|f  |該当なし(子音hに統合) |
|my  |該当なし(子音mに統合)  |
|ry  |該当なし(子音rに統合) |
|gy  |該当なし(子音gに統合) |
|j  |該当なし(子音zに統合) |
|by  |該当なし(子音bに統合) |
|py  |該当なし(子音pに統合) |
|v  |該当なし(子音bに統合) |

上記表では拗音を拗音でない子音に統合するなど、直感的に似ている子音は統合する処理をしています。可能であれば各子音同士の類似度を0~1の実数で定義しておいて重み付き編集距離を求めるのがベストだとは思います。
またア行とンとッの子音は本来無音（sp）が正しいのですが、ここではそれぞれ区別するために、a、N、qという記号を与えました。

上記表をベースにカナ一文字を子音に変換する関数をまず作り、それを使って、文字列全体を子音に変換します。

```Python
#受け取ったカナ１単位を母音に変換して返す
#入力はモウラ１単位に相当するカナ文字列（長さ１または２）
def char2vowel(text):
  t = text[0] #子音に変換するには最初の１文字を見れば良い
  if t in "アイウエオヤユヨワヲ":
    return "a"
  elif t in "カキクケコ":
    return "k"
  elif t in "サシスセソ":
    return "s"
  elif t in "タチツテト":
    return "t"
  elif t in "ナニヌネノ":
    return "n"
  elif t in "ハヒフヘホ":
    return "h"
  elif t in "マミムメモ":
    return "m"
  elif t in "ラリルレロ":
    return "r"
  elif t in "ガギグゲゴ":
    return "g"
  elif t in "ザジズゼゾヂヅ":
    return "z"
  elif t in "ダデド":
    return "d"
  elif t in "バビブベボヴ":
    return "b"
  elif t in "パピプペポ":
    return "p"
  elif t == "ッ":
    return "q"
  elif t == "ン":
    return "N"
  else:
    print("no match")
    return text

def kana2consonant(kana_list):
  output = []
  for v in kana_list:
    kana = char2consonant(v)
    output.append(kana)
  return output
```

#編集距離の計算
状況に応じて色々使い分けるため、いくつかの方法で編集距離を求める方法を定義しておきます。

##一般的な編集距離
一般的な定義通りの編集距離はeditdistanceライブラリのevalという関数で求められます。使い方は文字列を２つ引数として入れるだけです。

```Python
import editdistance as ed
kana_list1 = ["コ”,"ン","ニ","チ","ワ"]
kana_list2 = ["コ”,"ン","バ","ン","ワ"]
dist = ed.eval(kana_list1,kana_list2)
print(dist)#出力は2
```

##置換のみによる編集距離（ハミング距離）
挿入、削除ができず置換のみが可能なときの編集距離（[ハミング距離](https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%9F%E3%83%B3%E3%82%B0%E8%B7%9D%E9%9B%A2))を求めることもできます。
これは文字列Aと文字列Bを頭から１文字ずつ比較して、違った文字の個数を求めることに相当します。挿入と削除、つまり文字列長を変える操作ができないので、比較する２つの文字列の長さが等しいときにのみ使えることに注意してください。

発音の類似度という観点からは、同じタイミングで同じ音が登場していることが強い効果を持つ可能性があります。この効果を重視する場合には、置換のみによる編集距離を採用することにメリットがあります。また、頭から順番に比較するだけなので、一般的な編集距離よりも計算量が節約できるメリットもあります。

```Python
#置換のみによる編集距離を求める
def replace_ed(kana_list1, kana_list2):
  if len(kana_list1) != (kana_list2): #kana_list1とkana_list2の文字列長が異なるとき警告を出す
    print("warning: length of kana_list1 is different from one of kana_list2")
  dist = 0
  for k1,k2 in zip(kana_list1, kana_list2):
    if k1 != k2:
      dist += 1
  return dist
```

##相対編集距離
編集距離は文字列が長いほど大きい値となる傾向があるため、絶対的な類似度として扱いたいときには、文字列長で規格化したほうが適している可能性があります。
一般的な編集距離、置換のみによる編集距離を、文字列長で規格化した値を求めるコードは下記です。

```Python
#一般的な相対編集距離(kana_list1の長さで規格化)
def relative_ed(kana_list1, kana_list2):
  dist = ed.eval(kana_list1, kana_list2)
  dist /= len(kana_list1)
  return dist

#置換のみによる相対編集距離(kana_list1の長さで規格化)
def relative_replace_ed(kana_list1, kana_list2):
  dist = replace_ed(kana_list1, kana_list2)
  dist /= len(kana_list1)
  return dist
```
なお、比較する２つの文字列のうち、どちらの長さを基準とするかは一考の余地があります。例えば、特定の単語Aがあって、単語Aといくつかの単語候補の類似度を求めたい場合には、単語Aの長さを基準とするのが良い気がします。特に基準となる単語を考えない場合は、２つの単語の長さの平均値を使ったほうがよいかもしれません。
今回は、１つ目の引数の単語の文字列長で規格化するコードを示しました。

##カナ、母音、子音の編集距離の計算
ここまでのコードを組み合わせて、カナ、母音、子音の編集距離を求める関数を作ります。
母音の編集距離は、カナを母音に変換してから編集距離を求めればよいです。子音も同様です。
今まで紹介した内容から
(絶対 or 相対) x (一般的 or 置換のみ) x (カナ or 母音 or 子音)
ということで、１２通りの編集距離が考えられます。
目的に応じて、必要な関数を作成してもらえたらと思います。
ここでは１２個例を示すと長くなるので、フラグ引数によって出力を分岐する関数の例を示します。入力は「入力」節で上げた条件を満たす、カタカナ文字列とします。

```Python
#text1, text2: 一意に発音できるカタカナ文字列
#is_relative: False、Trueのときそれぞれ絶対、相対編集距離を求める
#ed_type: "normal","replace"のときそれぞれ一般的な、置換のみによる編集距離を求める
#kana_type: "kana","vowel","consonant"のときそれぞれ、カナ、母音、子音の編集距離を求める
def calc_ed(text1, text2, is_relative=False, ed_type="normal", kana_type="kana"):
  #入力をモウラの単位に分割
  kana_list1 = mora_wakachi(text1)
  kana_list2 = mora_wakachi(text2)

  #長音を母音に変換
  kana_list1 = bar2vowel(kana_list1)
  kana_list2 = bar2vowel(kana_list2)

  #kana_typeに応じて何もしない、または母音や子音に変換
  if kana_type=="kana":
    pass
  elif kana_type == "vowel":
    kana_list1 = kana2vowel(kana_list1)
    kana_list2 = kana2vowel(kana_list2)
  elif kana_type == "consonant":
    kana_list1 = kana2consonant(kana_list1)
    kana_list2 = kana2consonant(kana_list2)
  else:
    print("warning: kana_type is invalid")

  #ed_typeに応じた編集距離を求める
  dist = 0
  if ed_type == "normal":
    dist = ed.eval(kana_list1, kana_list2)
  elif ed_type == "replace": 
    dist = replace_ed(kana_list1, kana_list2)
  else:
    print("warning: ed_type is invalid")

  #is_relativeがTrueならkana_list1の文字列長で規格化する
  if is_relative: 
    dist /= len(kana_list1)

  return dist
```


#コード全体
コピペ用のコード全体です。
管理しやすいようにクラスにしています。

```Python
import re
import editdistance as ed

class EditDistanceUtil():
  def __init__(self):
    self.re_mora = self.__get_mora_unit_re()

  #モウラ単位に分割するための正規表現パターンを得る
  def __get_mora_unit_re(self):
    #各条件を正規表現で表す
    c1 = '[ウクスツヌフムユルグズヅブプヴ][ヮァィェォ]' #ウ段＋「ヮ/ァ/ィ/ェ/ォ」
    c2 = '[イキシシニヒミリギジヂビピ][ャュェョ]' #イ段（「イ」を除く）＋「ャ/ュ/ェ/ョ」
    c3 = '[テデ][ャィュョ]' #「テ/デ」＋「ャ/ィ/ュ/ョ」
    c4 = '[ァ-ヴー]' #カタカナ１文字（長音含む）

    cond = '('+c1+'|'+c2+'|'+c3+'|'+c4+')'
    re_mora = re.compile(cond)
    return re_mora
  
  #カタカナ文字列をモウラ単位に分割したリストを返す
  def mora_wakachi(self, kana_text):
    return self.re_mora.findall(kana_text)

  def char2vowel(self, text):
    t = text[-1] #母音に変換するには最後の１文字を見れば良い
    if t in "アカサタナハマヤラワガザダバパァャヮ":
      return "ア"
    elif t in "イキシチニヒミリギジヂビピィ":
      return "イ"
    elif t in "ウクスツヌフムユルグズヅブプゥュヴ":
      return "ウ"
    elif t in "エケセテネヘメレゲゼデベペェ":
      return "エ"
    elif t in "オコソトノホモヨロヲゴゾドボポォョ":
      return "オ"
    elif t == "ン":
      return "ン"
    elif t == "ッ":
      return "ッ"
    else:
      print(text, "no match")
      return text

  #長音を母音に変換
  #入力はモウラの単位で分割されたカナのリスト
  def bar2vowel(self, kana_list):
    output = []
    output.append(kana_list[0])
    #最初に長音がくることは想定しないので、２番めの要素からループを始める
    for i,v in enumerate(kana_list[1:]):
      if v == "ー":
        kana = self.char2vowel(output[i])#長音が連続した場合に対応するために念の為、outputから直前の要素を取得する
      else:
        kana = v
      output.append(kana)
    return output

  #カナを母音に変換する
  def kana2vowel(self, kana_list):
    output = []
    for v in kana_list:
      kana = self.char2vowel(v)
      output.append(kana)
    return output

  #受け取ったカナ１単位を子音に変換して返す
  #入力はモウラ１単位に相当するカナ文字列（長さ１または２）
  def char2consonant(self, text):
    t = text[0] #子音に変換するには最初の１文字を見れば良い
    if t in "アイウエオヤユヨワヲ":
      return "a"
    elif t in "カキクケコ":
      return "k"
    elif t in "サシスセソ":
      return "s"
    elif t in "タチツテト":
      return "t"
    elif t in "ナニヌネノ":
      return "n"
    elif t in "ハヒフヘホ":
      return "h"
    elif t in "マミムメモ":
      return "m"
    elif t in "ラリルレロ":
      return "r"
    elif t in "ガギグゲゴ":
      return "g"
    elif t in "ザジズゼゾヂヅ":
      return "z"
    elif t in "ダデド":
      return "d"
    elif t in "バビブベボヴ":
      return "b"
    elif t in "パピプペポ":
      return "p"
    elif t == "ッ":
      return "q"
    elif t == "ン":
      return "N"
    else:
      print(text, "no match")
      return text
  #カナ文字列を子音にして返す
  def kana2consonant(self, kana_list):
    output = []
    for v in kana_list:
      kana = self.char2consonant(v)
      output.append(kana)
    return output
  
  #置換のみによる編集距離を求める
  def replace_ed(self, kana_list1, kana_list2):
    if len(kana_list1) != len(kana_list2): #kana_list1とkana_list2の文字列長が異なるとき警告を出す
      print("warning: length of kana_list1 is different from one of kana_list2")
    dist = 0
    for k1,k2 in zip(kana_list1, kana_list2):
      if k1 != k2:
        dist += 1
    return dist
        
  #text1, text2: 一意に発音できるカタカナ文字列
  #is_relative: False、Trueのときそれぞれ絶対、相対編集距離を求める
  #ed_type: "normal","replace"のときそれぞれ一般的な、置換のみによる編集距離を求める
  #kana_type: "kana","vowel","consonant"のときそれぞれ、カナ、母音、子音の編集距離を求める
  def calc_ed(self, text1, text2, is_relative=False, ed_type="normal", kana_type="kana"):
    #入力をモウラの単位に分割
    kana_list1 = self.mora_wakachi(text1)
    kana_list2 = self.mora_wakachi(text2)
  
    #長音を母音に変換
    kana_list1 = self.bar2vowel(kana_list1)
    kana_list2 = self.bar2vowel(kana_list2)
  
    #kana_typeに応じて何もしない、または母音や子音に変換
    if kana_type=="kana":
      pass
    elif kana_type == "vowel":
      kana_list1 = self.kana2vowel(kana_list1)
      kana_list2 = self.kana2vowel(kana_list2)
    elif kana_type == "consonant":
      kana_list1 = self.kana2consonant(kana_list1)
      kana_list2 = self.kana2consonant(kana_list2)
    else:
      print("warning: kana_type is invalid")
  
    #ed_typeに応じた編集距離を求める
    dist = 0
    if ed_type == "normal":
      dist = ed.eval(kana_list1, kana_list2)
    elif ed_type == "replace": 
      dist = self.replace_ed(kana_list1, kana_list2)
    else:
      print("warning: ed_type is invalid")
  
    #is_relativeがTrueならkana_list1の文字列長で規格化する
    if is_relative: 
      dist /= len(kana_list1)  
    return dist  
    
  #カナの編集距離を求める
  def kana_ed(self, text1,text2):
    return self.calc_ed(text1, text2, False, "normal", "kana")
  
  #母音の編集距離を求める
  def vowel_ed(self, text1,text2):
    return self.calc_ed(text1, text2, False, "normal", "vowel")
  
  #子音の編集距離を求める
  def consonant_ed(self, text1,text2):
    return self.calc_ed(text1, text2, False, "normal", "consonant")    
    
  #カナの置換のみによる編集距離を求める
  def kana_replace_ed(self, text1,text2):
    return self.calc_ed(text1, text2, False, "replace", "kana")
  
  #母音の置換のみによる編集距離を求める
  def vowel_replace_ed(self, text1,text2):
    return self.calc_ed(text1, text2, False, "replace", "vowel")
  
  #子音の置換のみによる編集距離を求める
  def consonant_replace_ed(self, text1,text2):
    return self.calc_ed(text1, text2, False, "replace", "consonant")    
    
  #カナの相対編集距離を求める
  def relative_kana_ed(self, text1,text2):
    return self.calc_ed(text1, text2, True, "normal", "kana")
  
  #母音の相対編集距離を求める
  def relative_vowel_ed(self, text1,text2):
    return self.calc_ed(text1, text2, True, "normal", "vowel")
  
  #子音の相対編集距離を求める
  def relative_consonant_ed(self, text1,text2):
    return self.calc_ed(text1, text2, True, "normal", "consonant")    
    
  #カナの置換のみによる相対編集距離を求める
  def relative_kana_replace_ed(self, text1,text2):
    return self.calc_ed(text1, text2, True, "replace", "kana")
  
  #母音の置換のみによる相対編集距離を求める
  def relative_vowel_replace_ed(self, text1,text2):
    return self.calc_ed(text1, text2, True, "replace", "vowel")
  
  #子音の置換のみによる相対編集距離を求める
  def relative_consonant_replace_ed(self, text1,text2):
    return self.calc_ed(text1, text2, True, "replace", "consonant")    
  
if __name__=="__main__":
  edu = EditDistanceUtil()
  text1 = "コンニチワ"
  text2 = "ワコンタラ"

  print("normal edit distance")
  print(edu.kana_ed(text1,text2))
  print("")
  print(edu.kana2vowel(text1), edu.kana2vowel(text2))
  print(edu.vowel_ed(text1,text2))
  print("")
  print(edu.kana2consonant(text1), edu.kana2consonant(text2))
  print(edu.consonant_ed(text1,text2))
  
  print("")
  print("replace edit distance")
  print(edu.kana_replace_ed(text1,text2))
  print("")
  print(edu.kana2vowel(text1), edu.kana2vowel(text2))
  print(edu.vowel_replace_ed(text1,text2))
  print("")
  print(edu.kana2consonant(text1), edu.kana2consonant(text2))
  print(edu.consonant_replace_ed(text1,text2))
  
  print("")
  print("relative normal edit distance")
  print(edu.relative_kana_ed(text1,text2))
  print("")
  print(edu.kana2vowel(text1), edu.kana2vowel(text2))
  print(edu.relative_vowel_ed(text1,text2))
  print("")
  print(edu.kana2consonant(text1), edu.kana2consonant(text2))
  print(edu.relative_consonant_ed(text1,text2))
  
  print("")
  print("relative replace edit distance")
  print(edu.relative_kana_replace_ed(text1,text2))
  print("")
  print(edu.kana2vowel(text1), edu.kana2vowel(text2))
  print(edu.relative_vowel_replace_ed(text1,text2))
  print("")
  print(edu.kana2consonant(text1), edu.kana2consonant(text2))
  print(edu.relative_consonant_replace_ed(text1,text2))
```