Q&A
band, bondが1文字違いだから似ていると言うなら
aとoも1文字違いで似ています
「類似する」をどのくらいまで拡張するのか定義が必要です
こちらで下のようなデータベースがあります。
このデータベース（この質問の最下部）を元に、類似する単語同士をグループ化して出力したいと考えています。
たとえば、
accent, access
aggression, congression, regression
avenue, revenue
band, bond
border, burden（離れた1文字違いが2箇所）
bash, cash, dash, hash
complain, complaint
era, erase
を自動的に判定できるような（例えば上のようなフォーマットで出力可能な）プログラムを作成したいと思います。
For文を使えば、Javaでもできそうかとはおもうのですが、Pythonなどは自然言語処理に強いというお話を聞きました。
特に「（離れた1文字違いが2箇所）」を判別することまでできるのかどうかについては関心があります。
処理に用いるプログラミング言語は何でも構いません。
よろしくお願いいたします。
下記はMySQLとなっておりますが、DBの種類が別でも構いません。
MySQL
1absence 2accent 3access 4aggression 5avenue 6band 7bash 8bond 9border 10burden 11campaign 12candidate 13cash 14colleague 15colony 16committee 17companion 18complain 19complaint 20confusion 21congression 22courage 23crash 24critic 25dash 26description 27disadvantage 28ecology 29editor 30emotion 31equality 32era 33erase 34harm 35hash 36mediator 37motion 38prescription 39recess 40refusion 41regression 42revenue 43
例えば abcd abef ghef の三種類の単語が対象の場合、1 番目と 2 番目は 2 文字違いで、2 番目と 3 番目も 2 文字違いです。しかし、1 番目と 3 番目は 4 文字違いです。
この場合、1 番目と 3 番目は全文字違っているので同じグループには入れられません。では 2 番目はどのグループに入れるべきでしょうか？
もう一度目的を分析して仕様を見直してください。グループ化で目的が達成できますか？
回答4件
0
ベストアンサー
レーベンシュタイン距離（レーベンシュタインきょり、英: Levenshtein distance）は、二つの文字列がどの程度異なっているかを示す距離の一種である。
ライブラリが存在するようです。
編集距離 (Levenshtein Distance)をpython で求める - Qiita
ですが、総当りする必要があるでしょうから、うまく枝刈りなどをしないと計算量が爆発するかもしれません。
投稿2019/06/13 01:29
総合スコア36115
いろいろとありがとうございます。とても参考になりました。
ご質問者のご判断にケチをつけるわけではないのですが、個人的にはクラスタリングに触れているhayataka2049さんがBAだと思います。
0
結果の善し悪しは別として、これくらいのコードでそこそこの結果は得られます。
python
1from collections import defaultdict 2 3from sklearn.feature_extraction.text import CountVectorizer 4from sklearn.cluster import KMeans 5 6with open("data.txt") as f: 7 data = f.read().splitlines() 8 9cv = CountVectorizer(analyzer="char", ngram_range=(1, 3), 10 min_df=0.05) 11X = cv.fit_transform(data) 12 13km = KMeans(n_clusters=12) 14y = km.fit_predict(X) 15 16result = defaultdict(list) 17for word, label in zip(data, y): 18 result[label].append(word) 19 20for group in result.values(): 21 print(*group, sep=", ") 22 23""" => 24accent, access, recess 25emotion, motion 26band, bond, border, courage, era, erase, harm 27aggression, congression, regression 28campaign, companion, complain, complaint 29colleague, colony, ecology 30committee, critic, editor, equality, mediator 31bash, cash, crash, dash, hash 32description, prescription 33absence, avenue, burden, revenue 34candidate, disadvantage 35confusion, refusion 36""" 37
説明
文字レベル1,2,3-gramで特徴量を作り、k平均法でクラスタリングしただけです。
これだと同じグループになる基準どうこうという議論はほぼできないのですが、それでも困らないのであれば簡単で有効な方法です。特徴量の作り方をいじって傾向を変えることもできます（2-gram以上だけ使う、tf-idfを使うなどが良いかも）。
投稿2019/06/13 01:29
編集2019/06/13 01:53
総合スコア30933
編集距離を使ってグルーピングのルールもクラスタリングを使わない方法で決めた方がまっとうなアプローチ、という話は当然あるのですが、簡単な方法で・・・
いろいろとありがとうございます。とても参考になりました。
0
修正依頼でのyambejpさんに同意しますが、
「どのぐらいの差まで許容するか」にかかってくると思います。
多分、質問者さんがやりたい処理は、「N文字以上同じものがある場合、同じグループと想定する」なんじゃないかと考えました。
なので、a と o は別物。そして、band と bond は b*nd で一致するので同じグループ。
とかかなと。
それなら正規表現でやるか、一工夫必要になりますね。
正規表現のほうはあまり使っていません。( C言語にはそういうのは無いし、C++にはありますが、私自身が使っていないので... )
ですが、Regular Expression というので、RegEx とか Reg とかそういうクラスやメソッドがあるはずなので、それを使う。
(言語やライブラリによって違う)
アルゴリズムという意味では、一工夫は必要。
今、私が質問文での印象は、「N文字以上同じものがある場合、同じグループと想定する」なので、
単純に、カウント方式(名称は適当)で行う。
ほかの方の過去質問ですが。
つ 単語の種類がいくつあるか表示する方法を教えてください。
この私の回答にすでに書いています。
この方法をもとにさらに一工夫を加えます。
「true(もしくは1以上)になっているものがN個以上」であれば「同じグループ」とみなす。
みたいに。
ただし、定義によって異なります。
例えば、a と o を同類とみなす。とか。( 上にちょこっと出ているだけとか )
そういう定義によっては違ってきます。
投稿2019/06/13 01:32
総合スコア4958
0
使ったことないけど、別のアプローチで
無料であらゆる辞書がダウンロードできる - 「EPWING」とは? を使えないか調べてみては？
投稿2019/06/13 01:14
総合スコア16415
あなたの回答
tips
プレビュー
