【Python】コラ用に遊戯王カード名の組み合わせを自動検索するためのツールを作成しました【ソース公開】

# 追記

コードを綺麗に書き直したものを[GitHubで公開](https://github.com/YSRKEN/word_collage_maker)しました。すぐ試せるように単語リスト付き。

# 概要

いつ頃からか、次のような画像コラがTwitterで流行りだしました。

<blockquote class="twitter-tweet" data-partner="tweetdeck"><p lang="und" dir="ltr"><a href="https://t.co/vhA4S5bXD0">pic.twitter.com/vhA4S5bXD0</a></p>&mdash; りめん⎷aおかもと (@wixossccc) <a href="https://twitter.com/wixossccc/status/1132635789374812160?ref_src=twsrc%5Etfw">May 26, 2019</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

見ての通り**遊戯王のカードを貼り合わせて任意の文字列を生成**しています。
というわけで、どのカードを貼り合わせればいいかを自動生成するコードを考えてみました。

# データ収集方法

まず、**遊戯王のカード名一覧のデータセット**を見つけてくる必要があります。
しかし、[遊戯王カードWiki](http://yugioh-wiki.net)や[公式データベース](https://www.db.yugioh-card.com/yugiohdb/?request_locale=ja&request_device=sp)などを見る限り、「カードパックごとの一覧」はあっても「全カード一覧」はなかなか見つかりません(全カードの枚数から考えると当然ではあるが)。
そのため、頑張ってコピペするか、スクレイピングするコードを書くなどして対処しましょう。幸い私の場合、[デュエルリンクス](https://www.konami.com/yugioh/duel_links/ja/)のカード名一覧をなんとかして入手できました。([著作権](https://www.konami.com/jobs/ja/jk/list/adm/detail.php?job_code=17)が怖いのでカード名リストは公開しません)

# 自動生成する方法

Twitterを見る限り、「カード名の1文字だけ使用する」といったことも可能なようです。
そのため、自由度は極めて高く、事実上任意の文字列を作り出せると言っても過言ではないでしょう。
ただ、さすがに「全部1文字だけで組む」とかは見た目的につまらなくなりそうなので、なるべく長い部分文字列を利用するコードにしたいです。
そこで思いついたのが、[N-gram](https://qiita.com/kazmaw/items/4df328cba6429ec210fb)を利用する方法です。まずこのように、部分文字列のデータをハッシュで蓄えておきます。

```python
# word_hash……部分文字列一覧。word_hash[部分文字列の長さ][部分文字列]={対象となるカードの番号一覧}
word_hash: Dict[int, Dict[str, Set[int]]] = {}

for name_index, name in enumerate(name_list):
    name_len = len(name)
    for begin_index in range(0, name_len):
        for end_index in range(begin_index + 1, name_len + 1):
            # begin_indexからend_indexまでの範囲で単語(name)を切り取ったのがslice_word
            slice_len = end_index - begin_index
            slice_word = name[begin_index:end_index]
            # ハッシュ(word_hash)に部分文字列(slice_word)を登録する
            if slice_len not in word_hash:
                word_hash[slice_len] = {}
            if slice_word not in word_hash[slice_len]:
                word_hash[slice_len][slice_word] = set()
            word_hash[slice_len][slice_word].add(name_index)
# 何文字までの部分文字列が取れたかを算出する
max_len = max(word_hash.keys())
min_len = min(word_hash.keys())
print(f'部分長：{min_len}-{max_len}')
```

次に、対象文字列を先頭から見ていって、なるべく長い文字列がヒットするように検索します。
先ほど書いたように、「部分文字列は1文字だけでもOK」というゆるいルールですので、[貪欲法](http://yugioh-wiki.net/?%A1%D4%EC%C5%CD%DF%A4%CA%D4%E4%A1%D5=)でパパっと当てはめてしまいましょう。
(以下のコードでは実装をサボったので、MIN_WORD_LENが大きすぎるなどして探索に失敗すると[無限ループ](http://yugioh-wiki.net/index.php?%A1%D4%A5%DD%A1%BC%A5%EB%A5%DD%A5%B8%A5%B7%A5%E7%A5%F3%A1%D5)になります)

```python
MAX_COUNT = 5  # 部分文字列に対する候補カード名を表示する最大件数
MIN_WORD_LEN = 1  # 部分文字列の最小長さ
query_text = 'ホワイト・シチューをライスニカケる者を抹殺するエルフの剣士'  # 合成対象の文字列
query_text_len = len(query_text)
p = 0
while p < query_text_len:
    for q in range(max_len, min_len - 1, -1):
        # pからqまでの範囲で単語(query_text)を切り取ったのがsliced_query_text
        sliced_query_text = query_text[p:p+q]
        sliced_query_text_len = len(sliced_query_text)
        # 枝刈り
        if sliced_query_text_len < MIN_WORD_LEN:
            continue
        if sliced_query_text_len not in word_hash:
            continue
        if sliced_query_text not in word_hash[sliced_query_text_len]:
            continue
        # ヒットしたので候補カード名一覧をMAX_COUNT件まで表示
        print(f'【{sliced_query_text}】：')
        count = 0
        for name_index in word_hash[sliced_query_text_len][sliced_query_text]:
            print(f'　{name_list[name_index]}')
            count += 1
            if count >= MAX_COUNT:
                break
        p += sliced_query_text_len
        break  # 2019/05/29に追記
```

# 探索例

まずは冒頭の文字列から。探索結果が次のように表示されますので、

```
【ホワイト・】：
　ホワイト・ホーンズ・ドラゴン
　ホワイト・ドルフィン
【シ】：
　ダークアサシン
　シンクロ・マテリアル
　ブラック・マジシャンズ・ナイト
　ハーフ・シャット
　アグレッシブ・クラウディアン
【チュー】：
　パワード・チューナー
　ライトニング・チューン
　ナチュラル・チューン
　格闘ねずみ　チュー助
　チューナーズ・ハイ
【を】：
　命を食する者
　虚無を呼ぶ呪文
　炎を食らう大亀
　二頭を持つキング・レックス
　ドラゴンを呼ぶ笛
【ライス】：
　ガーディアン・トライス
　閃光の双剣―トライス
【ニカ】：
　フレムベルグルニカ
　ボタニカル・ライオ
　ドリル・バーニカル
【ケ】：
　強欲なカケラ
　聖獣セルケト
　暗黒界の鬼神ケルト
　スペシャルハリケーン
　ロケットハンド
【る者】：
　黒羽を狩る者
　命を食する者
　魂を狩る者
　炎を操る者
　炎を支配する者
【を】：
　命を食する者
　虚無を呼ぶ呪文
　炎を食らう大亀
　二頭を持つキング・レックス
　ドラゴンを呼ぶ笛
【抹殺】：
　戦士抹殺
　無情の抹殺
　抹殺の使徒
【するエルフの剣士】：
　翻弄するエルフの剣士
```

ここから好きな文字列を選んでコラ画像を作ればいいです。例えば、

```
ホワイト・シチューをライスニカケる者を抹殺するエルフの剣士

[ホワイト・]ホーンズ・ドラゴン
　 闇の住人[シ]ャドウキラー
　　　　　　　[チュー]ン・ウォリアー
　　　　　　　　　 屍[を]貪る竜
　　　　　 閃光の双剣―ト[ライス]
　　　　　　　　 フレムベルグル[ニカ]
　　　　　　　　　　　デビル・クラー[ケ]ン
　　　　　　　　　　　　　　　　 魂を狩[る者]
　　　　　　　　　　　　　　　　　７つの武器[を]持つハンター
　　　　　　　　　　　　　　　　　　　　　　　 [抹殺]の使徒
　　　　　　　　　　　　　　　　　　　　　　　　 翻弄[するエルフの剣士]
```

といったふうに作成できます。他にもいろいろ作ってみましょう。

```
精神を刻む者ジェイス
＝[精神]統一
　翼[を]織りなす者
　破邪の[刻]印
　龍脈に棲[む者]
　[ジェイ]ドナイト
　グロ[ス]

ミミミンミミミンウーサミン
＝暗黒の[ミミ]ックLV1
　[ミン]ゲイドラゴン
　暗黒の[ミミ]ックLV3
　N・エアハ[ミン]グバード
　ララライ[ウー]ン
　[サ]イコ・デビル
　アロマージジャス[ミン]

メタルギアソリッド・ピースウォーカー
＝[メタル]デビルゾア
　フェニックス・[ギア]・フリード
　ブルーアイズ・[ソリッド・]ドラゴン
　森羅の実張り [ピース]
　[ウォー]ター・ドラゴン－クラスター
　サモンブレー[カー]
```

# 注意

- 言うまでもありませんが、**ミリシタやシャニマスなどのカード名でも同様にコラ画像の種に使えます**
- 暇な人は画像コラを作成する部分も自動作成してみると楽しいのではないでしょうか