2

Java で次の基本的なスライディング ウィンドウ アルゴリズムを実装しようとしています。私はそれの基本的な考え方を理解していますが、いくつかの言葉遣い、特に太字の文に少し混乱しています:

固定幅 w のスライディング ウィンドウがファイル全体を移動し、ファイル内のすべての位置 k で、その内容のフィンガープリントが計算されます。k をチャンク境界とする (つまり、Fk mod n = 0)。チャンク全体のハッシュを取得する代わりに、このチャンク内のスライディング ウィンドウの数値的に最小のフィンガープリントを選択します。次に、チャンク内でこのランダムに選択されたウィンドウのハッシュを計算します。直観的には、このアプローチにより、チャンク内の小さな編集が類似度の計算に与える影響が少なくなります。この方法では、署名内の指紋の数が文書の長さに比例する可変長の文書署名が作成されます。

以下のコード/結果をご覧ください。アルゴリズムの基本的な考え方を理解していますか? 太字のテキストに従って、「チャンク内のスライディング ウィンドウの数値的に最小のフィンガープリントを選択する」とはどういう意味ですか? 現在、チャンク全体をハッシュしています。

コード：

    public class BSW {

    /**
     * @param args
     */
    public static void main(String[] args) {
        int w = 15; // fixed width of sliding window
        char[] chars = "Once upon a time there lived in a certain village a little             
            country girl, the prettiest creature who was ever seen. Her mother was 
            excessively fond of her; and her grandmother doted on her still more. This 
            good woman had a little red riding hood made for her. It suited the girl so 
            extremely well that everybody called her Little Red Riding Hood."
                .toCharArray();

        List<String> fingerprints = new ArrayList<String>();

        for (int i = 0; i < chars.length; i = i + w) {

            StringBuffer sb = new StringBuffer();

            if (i + w < chars.length) {
                sb.append(chars, i, w);
                System.out.println(i + ". " + sb.toString());
            } else {
                sb.append(chars, i, chars.length - i);
                System.out.println(i + ". " + sb.toString());
            }

            fingerprints.add(hash(sb));

        }

    }

    private static String hash(StringBuffer sb) {
        // Implement hash (MD5)
        return sb.toString();
    }

}

結果：

0. Once upon a tim
15. e there lived i
30. n a certain vil
45. lage a little c
60. ountry girl, th
75. e prettiest cre
90. ature who was e
105. ver seen. Her m
120. other was exces
135. sively fond of 
150. her; and her gr
165. andmother doted
180.  on her still m
195. ore. This good 
210. woman had a lit
225. tle red riding 
240. hood made for h
255. er. It suited t
270. he girl so extr
285. emely well that
300.  everybody call
315. ed her Little R
330. ed Riding Hood.
4

3 に答える 3

2

それはスライディングウィンドウではありません。入力をばらばらなチャンクに分割しただけです。スライディング ウィンドウの例は次のとおりです。

Once upon a time
upon a time there
a time there lived
etc.
于 2013-09-11T16:09:53.103 に答える
1

私の理解では、簡単な答えはNOです（私は数年前にスライディングウィンドウアルゴリズムを研究したことがあるので、原則を覚えていますが、詳細は覚えていません。より洞察に満ちた理解があれば修正してください）。

アルゴリズム「スライディング ウィンドウ」の名前のとおり、ウィンドウはジャンプではなくスライドする必要があります。

at every position k in the file, the fingerprint of its content is computed

あなたの引用符で。つまり、ウィンドウは毎回 1 文字ずつスライドします。

私の知る限り、チャンクとウィンドウの概念は区別されるべきです。フィンガープリントとハッシュも同じである可能性がありますが、同じである必要があります。ハッシュをフィンガープリントとして計算するには費用がかかりすぎることを考えると、Rabin フィンガープリントの方が適切な選択だと思います。チャンクはドキュメント内のテキストの大きなブロックであり、ウィンドウはチャンク内の小さな部分を強調表示します。IIRC、スライディング ウィンドウ アルゴリズムは次のように機能します。

  1. テキスト ファイルは最初にチャンク化されます。
  2. チャンクごとに、ウィンドウ (実行中のケースでは 15 文字のブロック) をスライドさせ、テキストのウィンドウごとにフィンガープリントを計算します。
  3. これで、チャンクの長さに比例する長さのチャンクのフィンガープリントが得られました。

次は、フィンガープリントを使用して異なるドキュメント間の類似性を計算する方法ですが、これは私の知る限りです。OPで参照した記事へのポインターを教えてください。交換として、ドキュメントの類似性を計算するためのスライディング ウィンドウ アルゴリズムの分散を紹介するこの論文をお勧めします。

ふるい分け: ドキュメント フィンガープリントのローカル アルゴリズム

参照できるもう 1 つのアプリケーションはrsync、ブロック レベル (チャンクに対応) の重複排除を備えたデータ同期ツールです。仕組みについては、この短い記事を参照してください。

于 2013-09-11T16:22:46.623 に答える
0 
package com.perturbation;

import java.util.ArrayList;
import java.util.List;

public class BSW {

    /**
     * @param args
     */
    public static void main(String[] args) {
        int w = 2; // fixed width of sliding window
        char[] chars = "umang shukla"
                .toCharArray();

        List<String> fingerprints = new ArrayList<String>();

        for (int i = 0; i < chars.length+w; i++) {

            StringBuffer sb = new StringBuffer();

            if (i + w < chars.length) {
                sb.append(chars, i, w);
                System.out.println(i + ". " + sb.toString());
            } else {
                sb.append(chars, i, chars.length - i);
                System.out.println(i + ". " + sb.toString());
            }

            fingerprints.add(hash(sb));

        }

    }

    private static String hash(StringBuffer sb) {
        // Implement hash (MD5)
        return sb.toString();
    }

}

このプログラムはあなたを助けるかもしれません。そして、より効率的にするようにしてください

于 2013-10-17T07:56:16.027 に答える