csvファイルから単語をインポートして比較し、一文字だけ異なるものをアウトプットしたい

Question

前提・実現したいこと

Bob、Tom、Kevinなどの1万語以上の単語が含まれているcsvファイル(1列×1万超の行)があります。（各単語の長さは異なる場合があります。）これらの単語を比較して一文字だけ異なるものを全てアウトプットしたいと考えております。

入力例：
str1 [] = "dog"、str2 [] = "fog" H（str1、str2）= 1 ここで、"dog"と "fog"は1文字異なっておりますのでdogとfogをアウトプットできたらと思います。
また、str3 [] = "sport"、str4 [] = "sports", H（str3、str4）= 1 ここで、"sport"と "sports"は文字の長さが異なっておりますが、文字の長さが一文字違うと1文字異なると判定し、sportとsportsをアウトプットできたらと思います。

要件：
(1)csvファイルから一行ごとに単語を読む方法を設計する必要があります。
(2)可能であれば、Java、python、c++のいずれかの言語で求めることができたらと考えております。

試したこと

プログラミング初心者です。当初はJava8でハミング距離を使って求めようとしたのですが、そもそもハミング距離は同じ長さの単語同士の比較しか使えないことが判明しました。(csvファイルには異なる長さの単語が含まれています。)どんな方法でもよいのでcsvファイルから単語をインポートして比較し、一文字だけ異なるものをアウトプットしたいと思います。
一つの単語と残り全ての単語の比較ですとbig o notationがO(10,000 power of 10,000)になってしまい計算できなくなってしまいますので、まずは隣接する単語どうし比較できたらと思います。どうぞよろしくお願いいたします。

Comments

[cateye]

過不足も視野に入ってますか？　文字が足りないor文字が多い・・・e.g. "cat"と"cats"おなじだが1文字多いとか？　長さが同じでと言う規制があれば高速にできそうだけど・・・
回答もらってる内に・・・遅かったｗ

[kkkk4]

"cat"と"cats"おなじだが1文字多いは、一文字異なるという風に設計したいです。質問文で右のように述べました。⇒また、str3 [] = "sport"、str4 [] = "sports", H（str3、str4）= 1 ここで、"sport"と "sports"は文字の長さが異なっておりますが、文字の長さが一文字違うと1文字異なると判定し、sportとsportsをアウトプットできたらと思います。

[cateye]

だとすれば2文字多い（少ない）は2になっちゃうんですか？　であればもとの文字列長±２は見なくていい？
で、もとの文字列が２文字（１文字）の時は？？

[kkkk4]

はい、もとの文字列長プラマイ2はNGとの想定で進めています。

[cateye]

いずれにしても文字列長でふるい分けて、その後文字列の比較すれば少しは効率上がりそうですね？

Answer 1

この辺ですかね。

レーベンシュタイン距離 - Wikipedia
Bitapアルゴリズム - Wikipedia

Comments

[cateye]

レーベンシュタインならO(1万×1万)ですね・・・どれくらい時間かかるか？
一回1msecで28時間ぐらい・・・最適化できるんかなぁ

[hayataka2049]

・長さの差が2以上あるものはハナから相手にしない
これで1桁くらい減りませんか。
・距離が2以上あるとわかった段階で切り上げ
うまく実装するともう1桁くらい減りそう。

意外とゴリ押しでも実用になりそうだなという気がしていますが、はたしてどうなるか。

[jimbe]

単純に比較で書いてみましたが,

import java.util.Arrays;
public class OneLetterDifference {
public static void main(String[] args) {
String[] words = new String[10000];
Arrays.fill(words, "AAAAAAAAAA");
long t = System.currentTimeMillis();
for(int i=0; i<words.length; i++) {
for(int j=i; j<words.length; j++) {
isOneLetterDifference(words[i], words[j]);
}
}
System.out.println((System.currentTimeMillis() - t)+" [ms]");
}
/** 1文字違いの時 true を返す */
static boolean isOneLetterDifference(String s1, String s2) {
int diffCount = Math.abs(s1.length() - s2.length());
for(int i=0; i<Math.min(s1.length(), s2.length()) && diffCount < 2; i++) {
if(s1.charAt(i) != s2.charAt(i)) diffCount ++;
}
return (diffCount == 1);
}
}
比較のみですが, 私の i5-2400S Win7-64 では 800[ms] 程でした.

[hayataka2049]

800msは朗報ですね。ただ、Javaは詳しくないんですが、それだとwordsの要素がすべて同じStringオブジェクトへの参照になりませんか？　キャッシュとへたしたら最適化が効いて、実力より速くなる気がします。

[swordone]

これだと"live"と"alive"のようなケースが弾かれそうだけど、それは想定内？
あと、間に一文字(hateとhasteみたいなの)は？

(3/12 ようやく間に一文字の実在単語例を発見)

[jimbe]

あぁ, すいません. テキトウすぎました.

[cateye]

800msならファイルからの読み込みのほうが・・・；；
・・・１０倍かかっても８秒なら許容範囲？
ディスクIOの待ち時間に何かできれば早くなるかも？
ちなみにjimboさんのプログラムは、うちの機械（AMD1600x+Linux mint+ NetBeans:java8）で、400msぐらいです。

[jimbe]

import java.util.Arrays;
public class OneLetterDifference {
public static void main(String[] args) {
System.out.println(isOneLetterDifference("foo", "-foo-")); //f
System.out.println(isOneLetterDifference("dog", "fog")); //t
System.out.println(isOneLetterDifference("dog", "dog")); //f
System.out.println(isOneLetterDifference("sport", "sports")); //t
System.out.println(isOneLetterDifference("live", "alive")); //t
System.out.println(isOneLetterDifference("abc", "abdc")); //t

String[] words = new String[10000];
Arrays.fill(words, "AAAAAAAAAA");
long t = System.currentTimeMillis();
for(int i=0; i<words.length; i++)
for(int j=i; j<words.length; j++)
isOneLetterDifference(words[i], words[j]);
System.out.println((System.currentTimeMillis() - t)+" [ms]");
}
/** 1文字違いの時 true を返す */
static boolean isOneLetterDifference(String s1, String s2) {
if(Math.abs(s1.length() - s2.length()) >= 2) return false; //2文字以上長い
int i1=0, i2=0, diffCount = 0;
for( ; i1<s1.length() && i2<s2.length(); i1++, i2++) {
if(s1.charAt(i1) != s2.charAt(i2)) {
diffCount ++;
if(s1.length() < s2.length()) i1--;
if(s1.length() > s2.length()) i2--;
}
}
if(i1 != s1.length() || i2 != s2.length()) diffCount ++;
return (diffCount == 1);
}
}
6件テストで ftfttt となりまして, 10000 ループで 750 [ms] 程と少し下がりました.
下がる要因は無いと思いますので, 100[ms] 程は上下しているかと思います><

Answer 2

・ファイルを１行づつ読み込み
・コンマで分割して要素に分解
・ファイルのすべての要素を取得
・２つの要素から比較検出して該当してるかどうかを出す関数を組む
・この関数を用いて、すべての要素の総当たりを行う

この手順で実現可能ですね

Comments

[kkkk4]

コメントありがとうございます。流れが理解できました。コンマで分割につきまして質問がございます。当方のセルは一列のみですが、それでも分割する必要はあるでしょうか？dog という単語を　d, o, gのcharacter毎に分割ということでしょうか？

[y_waiwai]

一般的にCSVというのは、コンマ区切りフォーマットのことなのでそう書きましたが、コンマで区切られていないのであればその必要はないです
１行づつ読み込むのは「JAVA １行読み込み」とかなんとかでぐぐると出てくると思います

[kkkk4]

ありがとうございました！早速試してみます！