多言語単語学習音声を作成したい！#3 Union-Find構造で単語群をグループ化する

この記事は多言語単語学習音声を作成したい！#1からシリーズになっています。

シリーズはこちらからご覧ください！

多言語単語学習音声を作成したい！#1
多言語単語学習音声を作成したい！#2 DeepLAPIを利用して単語翻訳をする
多言語単語学習音声を作成したい！#番外編 UUIDで単語を管理する
多言語単語学習音声を作成したい！#4 Text2SpeechAPIを用いて単語を音声化する

生成AI先生に伺ったところ、厳密にAとBが一致できるものはUnion-Findが有効とのことです。
今回のように概念的なものはもうちょっと複雑なアルゴリズムになるのが一般的らしいです。(ベクトルとか使うヤ～ツ)

これ以上複雑なものは僕の脳が耐えきれないので一旦Union-Findを利用します。

前回までの復習

1.複数の言語の単語帳が欲しい、音声で(#1)
2.単語群をDeepLで翻訳した(#2)

今回は似ている単語を同じグループにしちゃおう！
Man=男性
Man=男
なので音声で学習するときは「Man 男性、男」と発音してほしいわけです。

Union Findで解決しよう

図式での説明はAtcoderさんの下記リンクにあるスライドが分かりやすかったのでご確認ください。

例え話にすると
・AさんとBさんは親戚か調べたい
・Aさんの先祖の中にBさんの先祖もいるか確認しようとすると以下の挙動になってしまう

Aさんの親族の数だけ実行
    Aさんの親族α = Aさんの親族[i]
    Bさんの親族の数だけ実行
        Bさんの親族β = Bさんの親族[k]
        もし 親族α と 親族β が同一人物ならば:
            AさんとBさんは親戚！

Aさんの親族全員とBさんの親族全員を総当たりしても同一人物がいないならば:
    AさんとBさんは親戚ではない！

・・・これはあまりにも賢くない総当たりですね。

Union-Find構造は「最初に家系図作成して『Aさん家系図』と名付ける」
Bさんの親族の家系図作成中に『Aさん家系図』と合流したらBさんも『Aさん家系図』の中に入れる
→つまり親族！！

とする方法です。
(文章にすると分かりにくい説明ですね)

Union-Find構造をPythonで作成する

先人の偉大なプログラムを拝借します。

先人のプログラムを自分が読みやすく理解できるように一部改変したものがこちらです。

from collections import defaultdict


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = list(range(n))
        self.rank = [-1] * n

    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.par[x] > self.par[y]:
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x

    def size(self, x):
        return -self.par[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        members_list = []
        for i in range(self.n):
            i_root = self.find(i)
            if i_root == root:
                members_list.append(i)
        return members_list

    def roots(self):
        root_list = []
        for i in range(len(self.par)):
            x = self.par[i]
            if x < 0:
                root_list.append(i)
        return root_list

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members

    def __str__(self):
        lines=[]
        all_groups=self.all_group_members()
        for r,m in all_groups.items():
            line=f'{r}:{m}'
            lines.append(line)
        result='\n'.join(lines)
        return result

では今回のように単語数n×言語数Lの二重配列ではどのようにプログラムを動かすか
まず今回のデータは下記のようになっています。

GRADE	JA	EN-US	ES	FR	UK	ZH-HANS
0	朝寝坊	oversleeping	dormir demasiado	sommeil excessif	проспав	睡过头
0	いけない	wrong	equivocado	erroné	неправильно	错误的
0	行っていらっしゃい。	Go ahead.	Adelante.	Allez-y, allez-y.	Давай, йди.	去吧，去吧。

GRADEは0~4まであり平易な単語ほど数字が低い(らしいが、とてもそうは思えないな～)

また記載してみて発覚したのですが『便「交通の〜」』のように日本語そのものに解説がついていることもあり、解説部分は削除する必要がありそう。

削除は一旦別作業でひっそり行うとして本題のUnion-Find木に戻る。

グループ化の要件

何をもってグループとするかだが、英語で同じ単語になれば同じ意味の言葉にします。

グループ化を過剰にすると一回の読み上げで読まれる単語数が増えすぎるために、今回は特定の言語で行います。

また翻訳サイトの作成の仕方が英語を起点にしていることが多いらしく、中継点として充分役割を果たすと考えられる。

ではこれらを元にデータをUnion-Findでまとめます。

スプレッドシートから記載済みの情報を取得

import gspread
from oauth2client.service_account import ServiceAccountCredentials

def make_client():
    creds = ServiceAccountCredentials.from_json_keyfile_name(
        google_key_file_path, scope
    )
    gc = gspread.authorize(creds)
    return gc

def get_cells_values(sheet_id, sheet_name):
    google_client = make_client()
    spreadsheet = google_client.open_by_key(sheet_id)
    sheet = spreadsheet.worksheet(sheet_name)
    data = sheet.get_all_values()
    return data

読み取ったデータの変更等

uf = UnionFind(num_rows)

english_word_map = defaultdict(list)
for i, row in enumerate(data):
    # 比較しやすくするため、小文字に変換し、句読点を除去する
    en_word = row['EN-US'].lower().strip().rstrip('.')
    english_word_map[en_word].append(i)

# 4. 同じ英語単語を持つ行をUnionする
for en_word, row_ids in english_word_map.items():
    if len(row_ids) > 1:
        # リストの先頭の行を基準に、他のすべての行をunionする
        first_id = row_ids[0]
        for i in range(1, len(row_ids)):
            uf.union(first_id, row_ids[i])

# 5. 結果の表示
all_groups = uf.all_group_members()

for root_id, member_ids in all_groups.items():
    # このグループに含まれる全ての単語データを表示
    for row_id in member_ids:
        # data[row_id] は辞書 {'GRADE': '0', 'JA': '朝寝坊', ...}
        row_data = data[row_id]
        print(f"  Row {row_id}: JA='{row_data['JA']}', EN-US='{row_data['EN-US']}'")

この後まとめたデータをキレイにしてからスプレッドシートに記載しました。

一旦目的としていることは完了しました。

反省

まとめられたデータを見てやはり単語を「同じである」と判定するのは難しいと感じています。

"run"は一般的には「走る」と訳されますが「経営する」とも訳されます。
"fire"は名詞であれば「火」などになりますが、動詞であれば「解雇する」などと訳されます。

逆もあることを考えると同じ意味であればまとめるのはなかなかに難しそうです。。。

専門的なアルゴリズムもあるとは思いますが、勉強したい分野のとして優先順位は低いな～といった感じです。
またどこかで学習することがあればアップデートします。