Verfolgen Sie die ursprüngliche Position der transformierten Zeichenfolge in Java

Question

Ich arbeite an einer Implementierung eines Quellcode Plagiat Algorithmus (Winnowing-Algorithmus) und habe ein Problem, wo ich Hilfe brauche.

Beispiel: I habe eine Zeichenfolge

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

und verwandeln diese Zeichenfolge

test="blahelloblatestblablablayeahbla" 

und aus dieser Zeichenfolge I bauen kgrams beispielsweise 5-Gramm

blahe lahel ahell hello ellob llobl .... ahbla 

I speichern Sie die kgrams in einer Liste von Strings, möchten aber auch die Start- und Endposition fr speichern om den Originaltext jedes kgrams, damit ich am Ende jedes kgram wieder auf seine ursprüngliche Textposition verweisen kann.

EDIT:

Also meine Frage wäre, wie kann ich die Start- und Endposition eines kgram bekommen mir jemand da helfen? Hast du irgendeine Idee? Vielen Dank im Voraus.

Answer 1

Wenn Sie die Positionen aus der ursprünglichen Zeichenfolge möchten, können Sie die Nicht-Buchstaben zuerst nicht entfernen oder die Information ist verloren. Sie müssen entweder die kgrams in der ursprünglichen Zeichenfolge direkt suchen (mehr CPU-Zeit) oder die ursprüngliche Position jedes Buchstabens zusammen mit der geänderten Zeichenfolge speichern (mehr Speicherplatz).

Hier ist eine Implementierung des letzteren:

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; 
    } 
} 

Beispiel:

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]