MecabとDPマッチングで韻を見つけるシステムを作ってみた。

近年のフリースタイルダンジョン、ヒプノシスマイクなどが流行りHIPHOP、ラップが一般に多く浸透してきています。
その影響をモロに受けた私が何か作れないかと思い、今回このシステム作成を行いました。

### 追記
(2024/09/30) コメント等色々ないですが、コードを共有します。
https://github.com/platinum-valley/rhyme_detector

動作にはPythonライブラリ、MeCab、mecab-ipadic-neologdのインストールが必要です。
以下、参考。
> 必要Pythonライブラリ(コードを見た感じです。)
flask
numpy
requests
mecab-python3

https://github.com/neologd/mecab-ipadic-neologd/blob/master/README.ja.md

# はじめに
韻は簡単に言えば__母音が一致している__ことです。
「最高」、「対応」は母音が「アイオウ」であり、いわゆる__韻を踏む__ことができています。

また、長音「ー」、促音「ッ」、撥音「ン」は省略される。
「エイ」が「エー」、「オウ」が「オー」に変換できる。などのルールもあります。

韻を踏むことで歌詞にリズムが生まれ、聞き心地がよくなります。

入力単語から韻が踏める単語を提示するWebサービスは以下のものがあります。
[韻ノート](https://in-note.com/)
[韻検索-作詞支援ツール](https://kujirahand.com/web-tools/Words.php)

入力文章から韻を見つけるサービスや取り組みは見つからなかったのでやってみることにしました！
追記：[既に取り組まれている方](https://qiita.com/suzuki86/items/2a2801944a3e393464c7)がいらっしゃいました。サーベイ力が足りませんね。


# 進捗
入力した文章([from 韻ノート](https://in-note.com/rhyme_groups/850))に対して、韻を見つけることができました！
![eho03-zwnlm.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/927654/ca180102-6d8a-9a7a-bb34-2194709fc080.gif)

# 実験環境
- Python3.6
- Mecab 0.996
- mecab-ipadic-neologd (2020年12月4日時点最新版) 

# システムの流れ
![スクリーンショット 2020-12-08 0.21.24.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/927654/6b93d62b-8347-6dee-e7ba-35043f4b01de.png)


1. 入力文に対してMecabで読み仮名文を取得
2. 読み仮名文から母音文を変換
3. 母音文から同一の母音系列を探索。韻を見つける
4. 見つかった韻に対応する入力文中の文字列の提示

# Mecab
オープンソースの形態素解析エンジンです。[^1]
形態素解析のみならず読み仮名を取得できるため、これを使って母音文を作成します。
![スクリーンショット 2020-12-07 22.43.05.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/927654/6fcd71a8-e829-52e0-e72a-1e2e8f857618.png)

また、今回はMecab用のカスタム辞書mecab-ipadic-neologd[^2]を用います。
このカスタム辞書は定期的に更新され、固有名詞などの形態素解析が可能になっています。
例えば、「霜降り明星」「四千頭身」という最近流行の芸人コンビ名を形態素解析します。
カスタム辞書を使わないと、下のように固有名詞として形態素解析できていません。また、四千頭身に至っては正しい読みが取得できません。
![スクリーンショット 2020-12-07 23.04.22.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/927654/c113a873-5c27-8072-a101-575eae5f144f.png)
一方でmecab-ipadic-neologdを使うと、それぞれを固有名詞として正しい読みも得ることができました。
![スクリーンショット 2020-12-07 23.04.54.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/927654/fd088362-18e0-5b48-26a3-b06c171ac821.png)

この韻を見つけるシステムではMecabの形態素解析精度におんぶにだっこです。ほんとにオブリガード

# DPマッチング
動的計画法(Dynamic Programming)におけるマッチングの手法はタスクによって異なり、種類も多いようです。
今回は編集距離マッチングによって韻を見つけます。
編集距離（レーベンシュタイン距離）マッチングでは2つの文字列S,Tがあるときに、文字列Sに以下の処理を何回加えれば、文字列Tになるかを探索します。

- 置換： 文字列Sの１文字を好きな文字に入れ替える。
- 挿入： 文字列Sに好きな文字を挿入する。（空文字を好きな文字に置換する。）
- 削除： 文字列Sの１文字を削除する。(空文字に置換する)

例をあげると、「たいよう」と「たいおう」の編集距離を検索する場合は、以下のように初期化します。それぞれの文字列の先頭には空文字が入っています。
![スライド3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/927654/568d0fc9-264e-ce66-a453-4372ab3633c5.png)

次に```d(i, j)```に入る編集距離を計算します。
![スライド40.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/927654/e93ef6e1-a026-1604-b7de-ffee35cc3464.png)

ここでは隣接する既知の編集距離から```d(i,j)```に至る編集距離をそれぞれ計算します。
この結果、最も小さい編集距離が```d(i,j)```に入る。この場合、```d(i,j) = 0```となります。

- 挿入: ```d(i,j-1) + 1```
- 削除: ```d(i-1,j) + 1```
- 置換: ```d(i-1,j-1)) + cost```
    - ```i, j```に対応する文字が一致していれば```cost = 0```一致していなければ```cost = 1```


これを全てのマスで計算すると以下のように埋まります。右下の編集距離が最終的な編集距離となります。この場合は「よ」と「お」を置換するだけで一致するので__1__となります。

![スライド5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/927654/3d518f1c-c48c-0f5f-ee09-3daed5e24752.png)

長々とDPマッチングの説明をしましたが、ここから韻を見つけます。
ここでは、ある母音列と全ての母音列でマッチングを行います。
先の例と異なる点として、１行の初期化を全て０としています。これにより、全ての母音列のどこからでも検索を行うことができます。
![スライド6.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/927654/681aa983-f3e9-b561-bb31-0bb16184f198.png)

これを全マス埋めると以下のようになります。結果、一番下の行で0となっている点が、__編集距離が０=一致した文字列__を検索することができる。
![スライド7.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/927654/bb65f86b-0e54-85c1-c2b5-0cd7c70326b2.png)

これが2個以上の場合に韻を踏めていると判定しています。

# 実験
タンポポ feat.ZORN/KREVAの一部分の歌詞で韻を探してみました。実際に聞いてみて韻がかなり踏まれていることを確認して欲しいです！
https://youtu.be/iW-jDqNE6M0?t=83
![スクリーンショット 2020-12-08 2.16.50.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/927654/da080e58-632d-25b5-5d5c-373d2a3d7a15.png)
![スクリーンショット 2020-12-08 2.18.02.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/927654/03c0ed95-f448-85d3-1dc8-750aa4aecc0f.png)
![スクリーンショット 2020-12-08 2.19.02.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/927654/a99c2809-4f51-c16c-f970-fb590f61eab5.png)

米を「ベイ」と読んでしまっている。読みの修復はプログラムからは難しい。米→コメに変更すると拾える。
天下無双中→「エアウオウ」になっている。同母音の連続を集約すると拾える。一方で拾えなくなる韻も出てきそう。
とは言っても、多くの韻を見つけることはできている。

# 最後に
ここではMecabを使った読み仮名取得とDPマッチングによる韻検索を行うことで韻を見つけるシステムの構築を行いました。結果、形態素解析エンジンの読み仮名の取得ミスや母音の集約などの問題はあったものの、大体の韻を見つけることができました。

せっかくなのでwebアプリとしてデプロイしたかったですが、時間が足りませんでした。。。



[^1]: https://taku910.github.io/mecab/
[^2]: https://github.com/neologd/mecab-ipadic-neologd/
[^3]: https://takuti.me/ja/note/levenshtein-distance/