JS - run-length encoding

Najłatwiejszy algorytm kompresji. Poznajemy jak działa, jak go napisać. Zaczynajmy!

Cóż, tutaj nie ma co zgadywać, zobaczmy na funkcję:

const runLengthEncoding = (string) => {

    let result = '';
    let count = 1;
  
    for (let i = 0; i < string.length; i++) {
      let j = i + 1;
      while (string[i] === string[j]) {
        count++;
        if (count === 9) {
          j++;
          break;
        } else {
          j++;
        }
      }
      result = result.concat(`${count}${string[i]}`);
      count = 1;
      i = j - 1;
    }
    return result;
  }

A także na jej działanie:

console.log(runLengthEncoding("AAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCDDDDDDDDAABB"));
//9A9A7A9B3B7C8D2A2B

I teraz omówienie:

Są dwa wskaźniki, i oraz j
Wskaźnik i zaczyna od 0 i leci jak indeksy
Wskaźnik j to 1 większy od i
Tak długo jak litera pod j jest taka sama jak pod i j jest przesuwany i count zwiększany
count nie może być większy od 9 bo kompresja polega na tym, że pierwszy znak to ilość od 1-9, drugi to litera/znak
Niezależnie od tego czy count przekroczył 9 czy po prostu litera pod j się zmieniła, dodajemy count i literę do wyniku, resetujemy count, j już wskazuje na następną literę, ale jeszcze i musimy przestawić na indeks o jeden wcześniejszy niż j

Wytłumaczenie dlaczego nie można mieć więcej niż 9 kompresji. Cóż, dlatego:

109A

To jest jedno zero 9 A? A może 10 znaków 9? No generalnie cała kompresja się psuje od strony logicznej gdy burzymy założenie, że pierwsze to ilość, drugie to znak.

Nie mówiąc już o tym, że dwucyfrowe wydłużają kompresowany tekst. Ten algorytm też jest niespecjalnie wyszukany, zobaczmy na takie coś:

AAB --> 2A1B

Super kompresja po której tekst staje się dłuższy. Natomiast jest to swego rodzaju algorytm, który warto opanować zanim rzucimy się na trudniejsze, w celach edukacyjnych i lekkiego wprowadzenia zagadnień, o których nie mamy jeszcze pojęcia.

JS – run-length encoding