Java: usunąć continious segmentu zerami z tablicy bajtów

Question

Na przykład, powiedzmy, że chcę usunąć z tablicy wszystkie ciągłego segmenty 0 na dłużej niż 3 bajty

byte a[] = {1,2,3,0,1,2,3,0,0,0,0,4}; 
byte r[] = magic(a); 
System.out.println(r); 

wynik

{1,2,3,0,1,2,3,4} 

I chcesz zrobić coś w stylu wyrażeń regularnych w Javie, ale w tablicy bajtów zamiast łańcucha znaków.

Czy jest coś, co może mi pomóc w wbudowaniu (lub czy istnieje dobre narzędzie innej firmy), czy też muszę pracować od zera?

Łańcuchy to UTF-16, więc konwersja tam iz powrotem nie jest dobrym pomysłem? Przynajmniej jest dużo zmarnowanego narzutów ... prawda?

Answer 1

regex nie jest narzędziem do pracy, można zamiast tego należy wdrożyć, że od zera

Answer 2

Java Regex działa na CharSequences - można było CharBuffer zawinąć istniejącą tablicę bajtów (może być konieczne rzutowanie jej na char []?) I zinterpretować ją jako taką, a następnie wykonać w tym celu wyrażenie regularne?

Answer 3

Nie widzę, w jaki sposób regex byłby przydatny do robienia tego, co chcesz. Jedną z rzeczy, którą możesz zrobić, to użyć Run Length Encoding do kodowania tej tablicy bajtów, zastąpić każdą zmianę "30" (odczytać trzy 0) pustym łańcuchem i dekodować końcowy ciąg znaków. Wikipedia ma prostą implementację Java.

Answer 4

Chociaż istnieje uzasadnione ByteString biblioteka pływających wokół, nikt, że widziałem wdrożył ogólną bibliotekę regexp na nich.

Polecam rozwiązywania problemu bezpośrednio zamiast wdrażania bibliotekę regexp :)

Jeśli nie przekonwertować ciąg iz powrotem, to prawdopodobnie nie znajdzie żadnego istniejącego kodowanie, który daje podróż w obie strony dla 0 bajtów . W takim przypadku musisz napisać własną tablicę bajtową < -> konwertery łańcuchów; nie warte problemów.

Answer 5

byte[] a = {1,2,3,0,1,2,3,0,0,0,0,4}; 
String s0 = new String(a, "ISO-8859-1"); 
String s1 = s0.replaceAll("\\x00{4,}", ""); 
byte[] r = s1.getBytes("ISO-8859-1"); 

System.out.println(Arrays.toString(r)); // [1, 2, 3, 0, 1, 2, 3, 4] 

użyłem ISO-8859-1 (latin1), ponieważ, w przeciwieństwie do jakiegokolwiek innego kodowania,

• każdy bajt w zakresie 0x00..0xFF mapy do ważnego znaku, a

• każda tych znaków ma taką samą wartość liczbową jak kodowanie Latin1.

Oznacza to, że łańcuch jest tej samej długości co oryginalnej tablicy bajtów, można dopasować dowolny bajt o wartości numerycznej z \xFF konstruktem, można konwertować wynikowy ciąg z powrotem do tablicy bajtów bez utraty informacji .

Nie próbowałem wyświetlać danych w postaci , mimo że wszystkie znaki są poprawne, wiele z nich nie nadaje się do wydrukowania. Należy również unikać manipulowania danymi, gdy jest w formie ciągów; możesz przypadkowo zrobić kilka zastępczych sekwencji sekwencji lub inną konwersję kodowania, nie zdając sobie z tego sprawy. W rzeczywistości nie robiłbym tego w ogóle, ale nie o to prosiłeś.:)

Należy również pamiętać, że ta technika niekoniecznie będzie działać w innych językach programowania lub smakach wyrażeń regularnych. Musiałbyś przetestować każdy indywidualnie.

Answer 6

Proponuję przekonwertować tablicę bajtową na łańcuch, wykonując wyrażenie regularne, a następnie konwertując je z powrotem. Oto działający przykład:

public void testRegex() throws Exception { 
    byte a[] = { 1, 2, 3, 0, 1, 2, 3, 0, 0, 0, 0, 4 }; 
    String s = btoa(a); 
    String t = s.replaceAll("\u0000{4,}", ""); 
    byte b[] = atob(t); 
    System.out.println(Arrays.toString(b)); 
} 

private byte[] atob(String t) { 
    char[] array = t.toCharArray(); 
    byte[] b = new byte[array.length]; 
    for (int i = 0; i < array.length; i++) { 
     b[i] = (byte) Character.toCodePoint('\u0000', array[i]); 
    } 
    return b; 
} 

private String btoa(byte[] a) { 
    StringBuilder sb = new StringBuilder(); 
    for (byte b : a) { 
     sb.append(Character.toChars(b)); 
    } 
    return sb.toString(); 
} 

Bardziej skomplikowane transformacje sugerują użycie Lexera. Zarówno JavaCC, jak i ANTLR obsługują parsowanie/przekształcanie plików binarnych.

Answer 7

Chociaż pytam, czy reg-ex jest właściwym narzędziem do pracy, jeśli chcesz go użyć, proponuję zaimplementować opakowanie CharSequence na tablicy bajtów. Coś takiego (napisałem to bezpośrednio, nie skompilowałem ... ale masz pomysł).

public class ByteChars 
implements CharSequence 

... 

ByteChars(byte[] arr) { 
    this(arr,0,arr.length); 
    } 

ByteChars(byte[] arr, int str, int end) { 
    //check str and end are within range here 
    strOfs=str; 
    endOfs=end; 
    bytes=arr; 
    } 

public char charAt(int idx) { 
    //check idx is within range here 
    return (char)(bytes[strOfs+idx]&0xFF); 
    } 

public int length() { 
    return (endOfs-strOfs); 
    } 

public CharSequence subSequence(int str, int end) { 
    //check str and end are within range here 
    return new ByteChars(arr,(strOfs+str,strOfs+end); 
    } 

public String toString() { 
    return new String(bytes,strOfs,(endOfs-strOfs),"ISO8859_1"); 
    } 

Answer 8

Realizacja wykorzystaniem wyrażeniem, proponowane inne odpowiedzi wynosi do 8 razy wolniej niż naiwnych realizacji stosując pętlę kopie bajtach od wejścia do tablicy macierzy wyjściowej.

Implementacja kopiuje bajt tablicy wejściowej według bajtu. Jeśli zostanie wykryta sekwencja zerowa, indeks tablicy wyjściowej zostanie zmniejszony (przewinięty). Po przetworzeniu tablicy wejściowej, macierz wyjściowa jest nawet jeszcze raz kopiowana, aby przyciąć jej długość do faktycznej liczby bajtów, ponieważ pośrednia macierz wyjściowa jest inicjalizowana za pomocą długości tablicy wejściowej.

/** 
* Remove four or more zero byte sequences from the input array. 
* 
* @param inBytes the input array 
* @return a new array with four or more zero bytes removed form the input array 
*/ 
private static byte[] removeDuplicates(byte[] inBytes) { 
    int size = inBytes.length; 
    // Use an array with the same size in the first place 
    byte[] newBytes = new byte[size]; 
    byte value; 
    int newIdx = 0; 
    int zeroCounter = 0; 

    for (int i = 0; i < size; i++) { 
     value = inBytes[i]; 

     if (value == 0) { 
      zeroCounter++; 
     } else { 
      if (zeroCounter >= 4) { 
       // Rewind output buffer index 
       newIdx -= zeroCounter; 
      } 

      zeroCounter = 0; 
     } 

     newBytes[newIdx] = value; 
     newIdx++; 
    } 

    if (zeroCounter >= 4) { 
     // Rewind output buffer index for four zero bytes at the end too 
     newIdx -= zeroCounter; 
    } 

    // Copy data into an array that has the correct length 
    byte[] finalOut = new byte[newIdx]; 
    System.arraycopy(newBytes, 0, finalOut, 0, newIdx); 

    return finalOut; 
} 

Drugie podejście byłoby uniknąć niepotrzebnych kopii przez nawijanie pierwszego bajtu zerowego (trzy lub mniej), i kopiowanie tych elementów było ciekawe nieco wolniej niż w pierwszym podejściu.

Wszystkie trzy implementacje zostały przetestowane na procesorze Pentium N3700 z 1000 iteracjami na macierzy wejściowej 8 x 32KB z kilkoma liczbami i długością zerowych sekwencji. Najgorsza poprawa wydajności w porównaniu do metody wyrażeń regularnych wyniosła 1.5x szybsza.

Pełne stanowisko badawcze można znaleźć tutaj: https://pastebin.com/83q9EzDc