在 java 中跟踪转换字符串的原始位置

Question

我正在研究一个源代码抄袭算法（winnowing algorithm）的实现，遇到问题需要帮助。

示例：我有一个字符串

String test="blahello,,,,/blatestbla7234///§"§$%"%$\n\n23344)§()(§$blablayeahbla";

并将此字符串转换为

test="blahelloblatestblablablayeahbla"

然后根据这个字符串我构建了千克，例如 5 克

blahe  lahel  ahell hello  ellob  llobl .... ahbla

我将 kgrams 保存在一个字符串列表中，但也想保存每个 kgram 的原始文本的开始和结束位置，所以我可以在最后引用每个 kgram 回到它们的原始文本位置。

编辑：

所以我的问题是如何得到一个千克的开始和结束位置有人可以帮我吗？你有什么主意吗？提前致谢。

Answer 1

如果你想从原始字符串中得到位置，你不能先去除非字母，否则信息会丢失。您要么需要直接在原始字符串中找到 kgrams（更多 CPU 时间），要么将每个字母的原始位置与修改后的字符串一起存储（更多内存 space）。

这是后者的一个实现：

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

public class KGram {

    public final String str;
    public final int start;
    public final int end;

    public KGram(String str, int start, int end) {
        this.str = str;
        this.start = start;
        this.end = end;
    }

    @Override
    public String toString() {
        return "KGram[\"" + str + "\":" + start + "," + end + "]";
    }

    public static List<KGram> extractFrom(String input, int size) {
        char[] chars = new char[input.length()];
        int[] indexes = new int[input.length()];
        int len = 0;

        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (!Character.isLetter(c)) continue;

            chars[len] = c;
            indexes[len] = i;
            len++;
        }

        List<KGram> kgrams = new ArrayList<>();
        for (int i = 0, j = size - 1; j < len; i++, j++) {
            String str = new String(Arrays.copyOfRange(chars, i, j + 1));
            kgrams.add(new KGram(str, indexes[i], indexes[j]));
        }
        return kgrams;
    }
}

示例：

String test = "blahello,,,,/blatestbla7234///§\"§$%\"%$\n\n23344)§()(§$blablayeahbla";
List<KGram> kgrams = KGram.extractFrom(test, 5);

System.out.println(kgrams.get(4));  // prints KGram["ellob":4,13]
System.out.println(kgrams.get(26)); // prints KGram["ahbla":60,64]

在 java 中跟踪转换字符串的原始位置

Track original position of transformed string in java

java

string

transformation

plagiarism-detection