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

根据我的理解，简单的答案是否定的（我几年前曾经研究过滑动窗口算法，所以我只记得原理，而无法记住一些细节。如果你有更深入的理解，请纠正我）。

作为算法“滑动窗口”的名称，你的窗口应该是滑动而不是像它说的那样跳跃

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

在你的报价中。也就是说窗口每次滑动一个字符。

据我所知，应该区分块和窗口的概念。指纹和散列也应该如此，尽管它们可能相同。考虑到将哈希计算为指纹的成本太高，我认为拉宾指纹是一个更合适的选择。块是文档中的一大块文本，窗口突出显示块中的一小部分。IIRC，滑动窗口算法的工作原理如下：

  1. 文本文件首先被分块；
  2. 对于每个块，您滑动窗口（运行案例中的 15 个字符块）并为每个文本窗口计算它们的指纹；
  3. 您现在有了块的指纹，其长度与块的长度成正比。

接下来是如何使用指纹来计算不同文档之间的相似度，这不是我所知道的。您能否给我们指向您在 OP 中提到的文章的指针。作为交流，我推荐你这篇论文，它介绍了一种滑动窗口算法的方差来计算文档相似度。

Winnowing：文档指纹识别的本地算法

另一个你可以参考的应用是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 回答