Javaでcsvファイルを読み込んでハミング距離を求めるには？

Question

前提・実現したいこと

Javaでcsvファイルからハミング距離を求めるには？

Bob、Tom、Kevinなどの1万語以上の単語が含まれているcsvファイル(1列×1万超の行)があります。（各単語の長さは異なる場合があります。）
これらの単語からハミング距離を求め、ハミング距離が１のものを全てアウトプットしたいと思っています。

入力例：str1 [] = "dog"、str2 [] = "fog" H（str1、str2）= 1 ここで、"dog"と "fog"の間のハミング距離は1ですのでdogとfogをアウトプットできたらと思います。

要件：一行ごとに単語にcsvを読む方法を設計する必要があります。
Java、可能であればJava8のstreamを使って求めたいです。

発生している問題・エラーメッセージ

プログラミング超初心者です。ハミング距離を求めるために、まずはcsvファイルの読み込み、その後でハミング距離のフィルタリングを行うと思うのですが、具体的なコードの落とし込みができず、特にハミング距離のフィルタリングをどのように行うかが苦労しています。まずは、csvファイルを配列に変換した方がよろしいのか、それともリストを使うべきかなどご示唆を頂けますと幸いです。csvファイルの読み込みまでは自力でできましたので、ソースコードを以下に記します。

ソースコード

// read csv file and output
// reference:https://brushmyskills.com/java-8/read-csv-file-stream-java-8/
package hummingdistance;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.stream.Stream;

public class Hummingdistance {
    public static void main(String[] args) {
    String txtFileName = "sample.csv";
 
		// reading csv file into stream, try-with-resources
		try (Stream<String> stream = Files.lines(Paths.get(txtFileName))) {
 
			stream.forEach(System.out::println);
 
		} catch (IOException ioe) {
			ioe.printStackTrace();
		}
 
	}

Answer 1

特にハミング距離のフィルタリングをどのように行うかが苦労しています。

streamに対するフィルタリングで「得たい要素だけを残す」というイメージをお持ちだと思います。しかし、その先のどこで躓いているかがはっきりと質問に書かれていません。プログラミングというのは

(A) 解を得るためにとるべき手順を考える(複雑な問題をより単純な手順の組み合わせとして考える)
(B) 充分単純化した部分的な手順のそれぞれについて頭の中にある処理パターンに照らし具体的コードに落とす

というような段取りで書いていくものです。ご質問の内容では(A)(B)どちらが問題なのか(あるいは両方なのか)がわからないわけです。わからない点が曖昧であればあるほど「ゴールにたどり着くに足る充分な回答が得られる確率は下がる」ことに注意ください。

ただ(B)を考えるための「頭の中の引き出しにある処理パターン」が乏しいと(A)をすること自体も難しいであろうことから、多くの場合(A)(B)どちらについても知識が不足しているといえるかも知れません。

本件は最適化を前提とせずに素朴に実装するなら割と単純な問題なので(A)を整理する例を挙げてみました。論理の組み立て方は人それぞれなところもあるのであくまで一例と考えてください。以下は「streamを使って論理を組み立てる練習をする」「最適化は考えず素朴な論理とする」方針で考えてみたものです。

手順を考える例

• (A1) 全ての単語について「ハミング距離が1であるような他の単語があるかどうか」を条件にフィルタリングする

質問者さんはここまではイメージしておられます。

• (A2) ハミング距離は等しい長さの列に対して定義されているので、まず全ての単語を同じ長さのもの同士でグルーピングする

これはswordoneさんが述べておられることです。

• (A3) 長さがLであるような単語の集合(以下WS(L)と呼ぶ)の各要素について「WS(L)内にハミング距離が1であるような単語が存在する」ものだけ残す
• (A4) WS(L)内の特定の単語についてWS(L)内の単語と総当たりで「ハミング距離が1か」を調べる。

そういう単語が一つでも見つかれば(A3)の判定結果はtrueさもなくばfalseです。

• (A5) 同じ長さの2つの単語の同じ位置の文字が違っている数を数える(ハミング距離の計算)
• (A6) 2つの単語の同じ位置の要素同士を表すペアの列に変換し各ペアを文字同士が異なれば1、さもなくば0という整数に変換しそれぞれの結果を合計する

(A5)をstream風にとらえた手順です。

• (A7) ありえる全てのLに対してWS(L)について(A3)でフィルタリングした集合を連結する

大雑把ですが上のような感じで考えました。上記ぐらいにすると個々の問題はstreamの処理パターンを知っていれば具体的コードに落とせますが、上から下へ順番に書くというより「わかる部分からコードに落としそれをうまく組み合わせる」というイメージで行うと作り易いかも知れません。

コードを組み立てる

(A6)は本当はzip的な機能がほしいところですがJavaの標準ライブラリーにはないので別のアプローチで次のようにしてみます。

int hammingDistance(String w1, String w2) {
  assert s1.length() == s2.length(); // 前提
  return IntStream.range(0, w1.length())
    .map(i -> w1.charAt(i) != w2.charAt(i) ? 1 : 0)
    .sum();
}

(A4)はanyMatchを使えばこう書けます。

boolean pass(List<String> wsl, String word) {
  return wsl.stream().anyMatch(w -> hamminguDistance(word, w) == 1);
}

(A3)はfilterでよいですね。

static Stream<String> select1(List<String> wsl) {
  return wsl.stream().filter(word -> pass(word));
}

(A2)はswordoneさん回答にあるとおりです。
(A2)で生成できたMap<Integer, List<String>>の各値(List<String>)に基づき(A3)で生成したストリームを(A7)の目的のため全てくっつける計算をしたいのですがそんな場合はflatMapの出番です。

static Stream<String> makeFilteredWords(Map<Integer, List<String>> wslGroup) {
  return wslGroup.values().stream()
    .flatMap(wsl -> select1(wsl));
}

このあたりまで個々の論理がイメージ出来れば最後に全体を合成します。
コードが長ったらしくなるのでJava11以降前提とし、varとか新たなFileReaderを用いてみました。また前述したメソッドのうちひょっとしたら再利用するかも知れないhammngDistanceを除きメソッドとはせずにmainメソッドの中で閉じた処理にしています(select1をメソッドとする代わりにFunctionインスタンスにした)。

package hammingdistance;

import java.io.*;
import java.nio.charset.StandardCharsets;
import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class HammingDistance {
  public static void main(String[] args) throws IOException {
    var path = "words.csv";
    var cs = StandardCharsets.UTF_8;
    try (var br = new BufferedReader(new FileReader(path, cs))) {
      Function<List<String>, Stream<String>> select1 = wsl -> wsl.stream()
         .filter(word -> wsl.stream().anyMatch(w -> hammingDistance(word, w) == 1));
      String[] words = br
         .lines()
         .collect(Collectors.groupingBy(String::length))
         .values().stream()
         .flatMap(select1)
         .toArray(String[]::new);
      for (var word : words) {
        System.out.println(word);
      }
    }
  }

  private static int hammingDistance(String w1, String w2) {
    assert w1.length() == w2.length(); // 前提
    return IntStream.range(0, w1.length())
       .map(i -> w1.charAt(i) != w2.charAt(i) ? 1 : 0)
       .sum();
  }
}

テキトーに作成した1万語のランダムな単語に対し上記を実行すると1秒あまりかかりました。このスピードはあまり満足すべきものではありませんが、あくまで「素朴な論理で性能はあまり考えずに」という前提なのでよしとしました。

---

本回答は今後役に立つような何かのtipsを示せているとはいえず、「問題点が明確でない問いに対して答えだけ教えたよくない回答」のそしりをうけるかも知れません。書いていて自分でそう思いました。本当は「streamにはいくつかのお定まりのパターンがあること、それを頭の引き出しにためておいた状態でないと論理は書けないこと」を言おうとしたのですが・・・そんなコメントならしないほうがましに思えたので、どうせ書くなら「streamの論理を組み立てる雰囲気を伝えてみよう」と考えこのような回答をしてみた次第です。

Comments

[kkkk4]

手順を考える例まで詳細にご教示いただきありがとうございます。当方のIDEはJava11に対応しておらず、varのところで右記エラーが出てしまいます。Exception in thread "main" java.lang.RuntimeException: Uncompilable source code - シンボルを見つけられません。シンボル: クラス var
また、Function<List<String>, Stream<String>> select1 = wsl -> wsl.stream()の箇所でもえらーがでてしまいます。
加えて、assert s1.length() == s2.length(); もエラーが出てしまいますので、assert w1.length() == w2.length();と変更してもよろしいでしょうか？

[KSwordOfHaste]

最後のassertは自分のミスです。すみませんでした。回答の方は既に訂正しております。
jdk11で書いた点については質問者さんには不親切でしたね...。varは他の言語でも割と一般的な型名の省略に使えるキーワードです。実際の型は右辺(初期値)の型により自動的に決まります。varの代わりに型名を記述すればコンパイルエラーは解消できるようになります。
var path = "...";
=>
String path = "...";
などのように変更してください。
またJDK11より前にはFileReaderのコンストラクターにはCharsetを指定できないので
new FileReader(path, cs)
=>
new FileReader(path)
に変更し、変数csを削除してください。

[kkkk4]

回答ありがとうございます。無事動きました！がいくつかお伺いしたい点がございます。csvファイルの中の単語はほぼ小文字ですが、まれに大文字の単語もあり、その単語はどうやらうまく比較されていないようです。また、私のcsvファイル中の単語は基本的に5文字でその比較はうまくいっているのですが、3文字の単語どうしの比較、3文字と4文字の単語どうしの比較がうまくいっていないようです。何かご示唆がございましたらご教示いただけますと幸いです。

[KSwordOfHaste]

> まれに大文字の単語もあり、その単語はどうやらうまく比較されていない
自分の論理は大文字小文字を区別する前提です。大文字小文字を区別せずに比較したいなら比較前に文字を小文字(大文字でもいい)に変換したもの同士を比較するのが簡単です。
> 3文字の単語どうしの比較...うまくいっていない
プログラミングの質問において通常「うまくいっていない」という説明は曖昧すぎて相手に伝わりません。具体的に「こういう結果が期待だが実際はこうなる」と表現してください。

[kkkk4]

申し訳ございません。こちらの勘違いだったようです。お騒がせしました。。

[swordone]

要件変わってるんだから、新しい質問の方でやった方がいいですよ。

[kkkk4]

かしこまりました！

Answer 2

Streamは、コレクションなどの各要素に画一的な操作を行うためのものであり、今回のような｢要素同士の比較｣を行うには不向きです。
ただ、ハミング距離は文字数が同じ文字列のペアに対して定義されるようなので、｢同じ文字数の文字列をまとめる｣所まではStreamで出来ます。

        try (Stream<String> stream = Files.lines(Paths.get(txtFileName))) {
            Map<Integer, List<String>> map = stream.collect(Collectors.groupingBy(s -> s.length()))

        } catch (IOException ioe) {
            ioe.printStackTrace();
        }

Comments

[kkkk4]

ご回答ありがとうございます。ハミング距離は文字数が同じ文字列のペアに対して定義されることは、恥ずかしながら存じ上げませんでした。csvファイルには異なる文字列が含まれていますので、stream、ハミング距離以外の選択肢をJava以外の言語も含めて検討できたらと思います。

Answer 3

この辺は疎いので・・・以下参考にされたらどうでしょうレーベンシュタイン距離（Pascal風擬似言語あります）
「追記」
アルゴリズム欄に有るリンク先には、各言語での実装例があります。

Comments

[kkkk4]

ご回答ありがとうございます。レーベンシュタイン距離という方法論もあるのですね。ハミング距離にこだわりたいということではございませんので、ご案内頂いた内容なども含めて検討していきます！