質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.20%

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

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 827

kkkk4

score 13

前提・実現したいこと

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

Bob、Tom、Kevinなどの1万語以上の単語が含まれているcsvファイル(1列×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();
        }

    }
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

checkベストアンサー

+2

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

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の論理を組み立てる雰囲気を伝えてみよう」と考えこのような回答をしてみた次第です。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/03/05 11:21 編集

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

    キャンセル

  • 2019/03/05 11:30

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

    キャンセル

  • 2019/03/05 11:31

    かしこまりました!

    キャンセル

+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();
        }

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/03/04 10:07

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

    キャンセル

+1

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/03/04 10:05

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.20%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る