Kompresowanie tablic łańcuchowych
AKTUALIZACJA: Narzędzia przedstawione w tym poradniku zostały odtąd przepisane, ulepszone i zintegrowane z moim interpreterem Japt . W celu uzyskania najlepszych rezultatów zaleca się stosowanie tej sprężarki w stosunku do któregokolwiek z poniższych łączy. Wrócę do tej wskazówki, kiedy będę miał więcej czasu, i przepiszę ją z myślą o nowej sprężarce.
Wprowadzenie
Jeśli masz tablicę ciągów w kodzie, najbardziej oczywistym sposobem na skompresowanie byłoby uruchomienie każdego z nichOc
osobno. Na potrzeby tej wskazówki będziemy pracować z tablicą ["lollipop","marshmallow","nougat","oreo"]
, która początkowo waży 42 bajty. Uruchomienie każdego ciągu Oc
daje nam:
[`lo¥ipop`,`Ú\hÚaow`,`Í`,`eo`]
To teraz 33 bajty, przyzwoita oszczędność.
Krok 1
Ale możemy zrobić lepiej. Jeśli połączymy tablicę z ciągiem oddzielonym znakiem nowej linii, możemy pozbyć się nawiasów, przecinków i obcych znaków tylnych i podzielić się na linii nowej, aby uzyskać naszą tablicę. Zastosowanie tego do naszej przykładowej tablicy daje nam następujące możliwości:
`lo¥ipop
Ú\hÚaow
Í
eo`·
Do 26 bajtów teraz.
Krok 2
Ale możemy jeszcze lepiej! Możemy użyć małej litery do rozgraniczenia ciągów zamiast nowej linii, która może zostać uwzględniona w kompresji. z
nie jest używany w żadnym z naszych ciągów, więc wpuśćmy to i zobaczmy, jak sobie radzimy.
`lo¥ipopzÚ\hÚaowzÍzeo`qz
Ach, orzechy - nie ma poprawy; nasza liczba bajtów wzrosła o jeden! Nie może być inna litera można użyć, ale w zależności od strun, nie może być sporo, aby spróbować - w naszym przykładzie jest 11: b,c,d,f,j,k,q,v,x,y,z
. Wypróbowanie każdego z nich byłoby dość żmudne, i tu właśnie pojawia się to przydatne narzędzie ; podaj mu ciągi rozdzielone znakiem nowej linii, a on spróbuje rozgraniczać ciągi każdą literą, która nie jest zawarta w żadnej z nich, i wypisz:
- najkrótszy skompresowany ciąg,
- ogranicznik, którego używa, oraz
- jego długość.
Przeprowadzenie przez nas naszych ciągów próbek pokazuje, że b
daje najlepsze wyniki:
`lo¥ipáæqrÚaowbÍÞo`qb
I masz, mamy tylko 24 bajty.
Krok 3
Ale możemy zrobić jeszcze lepiej! Jeśli kolejność ciągów w tablicy nie ma znaczenia, być może istnieje inna permutacja w połączeniu z innym ogranicznikiem, który może działać jeszcze krócej. Jednak wypróbowanie każdej z tych możliwości będzie znacznie bardziej uciążliwe. Dzięki naszym 4 ciągom możesz wypróbować 24 różne kombinacje. Z każdą z 11 możliwych liter, które stają się 264! Właśnie wtedy to narzędzie wchodzi w grę. Ponownie podaj go jako ciągi rozdzielone znakiem nowej linii, a on wypróbuje każdą kombinację każdej permutacji i każdej litery ograniczającej, generując:
- kolejność ciągów w najkrótszym skompresowanym ciągu,
- skompresowany ciąg,
- ogranicznik, którego używa, oraz
- jego długość.
Running nasze przykładowe ciągi przez to pokazuje, że "nougat","oreo","lollipop","marshmallow"
ze b
jako ogranicznik daje najlepsze rezultaty, z ostatecznym rozrachunku tylko 23 bajtów z:
`ÍÞo½o¥ipáæqrÚaow`qb
Dodatkowa wskazówka: Kompresja tablic liczb całkowitych
Możesz zastosować tę samą zasadę do tablic liczb całkowitych, najpierw konwertując każdą z nich na wyższą bazę. Korzystając z tej próbki, tablica 36 bajtów:
[588181,156859,595676,475330,680474]
Możemy to zmniejszyć do 29 bajtów, najpierw konwertując go na tablicę podstawowych ciągów 32, a następnie uruchamiając przez pierwszy program do kompresji:
`huclt4p5r5ÛÊg62tkogq`qt mnH
Lub zaledwie 27 bajtów za pomocą drugiego programu:
`4p5Ïcl5ÛÊg62tkogq`qt mnH
Możesz być w stanie zapisać jeszcze jeden bajt lub 2, przenosząc konwersję liczb całkowitych na metodę, którą już uruchomiłeś na tablicy.
Notatki
- Nie zapomnij czynnikiem w 1 lub 2 dodatkowych bajtów
q<letter>(<space>)
kosztuje ponad ·
. Chociaż możesz użyć jednego ze skrótów Unicode, aby odzyskać bajt, w zależności od ogranicznika ( qÊ
jest taki sam, jak ql<space>
na przykład).
- Słowo ostrzeżenia przy korzystaniu z ostatniego narzędzia: im więcej masz łańcuchów, tym więcej będzie permutacji i tym wolniej program będzie działał, aż w końcu przestanie działać. Jak wyszczególniono powyżej, z naszymi 4 przykładowymi ciągami znaków i 11 możliwymi literami do wypróbowania, istnieje 264 możliwych kombinacji, zwiększ liczbę ciągów tylko o 1 z tymi samymi 11 literami i mamy już 1320 kombinacji do wypróbowania. (Możesz użyć tego narzędzia, aby policzyć liczbę kombinacji, jeśli chcesz).
Kredyty
- Oliver za inspirację do stworzenia narzędzi zawartych w tym poradniku.
- Produkty ETH do korekty.