PHPでしりとりWebサイトのアルゴリズム

Question

Q.知りたいこと

下記しりとりWebサービスを実現できるためのアルゴリズムを探しています。
検索した結果下記が近いのではないかと予想しております。
実装するに当たり理解するのが追いつかないので簡単に実装できる物がありましたら教えて下さい。

参考：おそらく下記の数式と
https://nlab.itmedia.co.jp/nl/articles/1107/19/news080.html
先述の深さ優先探索による塗りつぶし
https://www.slideshare.net/chokudai/dfs-49066641
上記2点を組み合わせるのが解ではないかと想像しております。

1. やりたいこと

1-1. Webサービスを作りたい
1-2. 1000弱の単語から自動でしりとりをする。
しりとりの始まりの単語(A)としりとりの終わりの単語(B)を任意で選択させる
1-3. 検索押下で自動でAからBまでをしりとりでつないでいく
1-4. Aは「ん」で終わる単語は選択させない
1-5. 細かいルール
最後の長音は母音とする
例：「ミキサー（ミキサア）」→「アイスクリーム」
最後の文字が拗音・促音（ぁ、ぃ、ぅ、ぇ、ぉ、ゃ、ゅ、ょ、っ）の場合、もとの文字（清音）に戻すルール
例：「滑車（かっしゃ）」→「やり」（清音に戻すルール）
最後の文字が濁音・半濁音の場合、「゛（濁点）」「゜（半濁点）」を取っていいルール

2. 処理終了の諸条件

2-1. 31以上単語がつながることが最低条件
2-2. AからBまで31以下で終了しか存在しなかった場合はマッチなしと表示

3.動作環境

3-1.HTML/JavaScript
3-2.PHP7
3-3.MySQL

4.作業完了内容

4-1.対象単語をMySQLに以下のカラムで登録
全単語の最初の文字と最後の字は抜き出してカラムに登録済み。
id,name,start_word,end_word,type1,type2,notes,del flag,create day,update day

      各カラム詳細
      id:通し番号
      name:単語名
      start_word:単語の始まり
      end_word:単語の終わり
      type1:単語のタイプ1
      type2:単語タイプ2
      notes:単語の備考
      del flag:削除フラグ
      create day:作成日
      update day:更新日    

5.検索方法

5-1.HTMLのテキストボックスに単語名をサジェストで表示するように設置
サジェストの中からテキストボックス1にAを選択させテキストボックス2にBを選択させる

Comments

[kyoya0819]

要は、ユーザーに最初の単語を選択してもらい、そこから自動でしりとりをしていき31回以上続けば表示し続かなかったら表示しないということでよろしいでしょうか？

[yoshige]

ご返信ありがとうございます。
最初と最後を選択して自動しりとりをして31回以上なら表示それ以下は非表示を考えております。
31以上はいくつにするとかまでは考えていません。

[退会済みユーザー]

ン　から始まるワード相当数あるけどね

https://kotobank.jp/idx/%E3%83%B3/1/

[yoshige]

ご返信いただきありがとうございます。
現在登録している単語は「ン」で始まる単語はございません

Answer 1

ちょっとサンプルデータが莫大すぎて書けないので、アルゴリズムだけ。

とりあえず、初めの文字を多い順に並べて、初めの文字と終わりの文字がそれぞれなるべく多くなるように選んでいけば、1番長く繋がるはずです。（ただし、選んだ後は再度選ばないようにする処理が必須）

Comments

[yoshige]

ご返信いただきありがとうございます。

まさにそのとおりだと思います。
おそらく下記の数式と
https://nlab.itmedia.co.jp/nl/articles/1107/19/news080.html
先述の深さ優先探索による塗りつぶし
https://www.slideshare.net/chokudai/dfs-49066641
を組み合わせるのが解なのだというところまでは思いついてます。

では具体的にどういうクエリーを投げるのか
処理をどうするかになると泥臭い実装になりそうです。

美しい実装ができないかなと頭を悩ませております。