Kompres data dengan tata bahasa bebas konteks

9

Dimungkinkan untuk mengompres beberapa jenis data, seperti teks manusia atau kode sumber, dengan tata bahasa garis lurus. Anda pada dasarnya membuat tata bahasa yang bahasanya memiliki satu kata - data yang tidak terkompresi. Dalam tugas ini, Anda harus menulis sebuah program yang mengimplementasikan metode pemadatan data ini.

Memasukkan

Input adalah string dengan panjang tidak lebih dari 65535 byte. Dijamin, bahwa input cocok dengan ekspresi reguler [!-~]+(yaitu setidaknya satu karakter ASCII yang dapat dicetak tidak termasuk spasi).

Contoh input adalah

abcabcbcbcabcacacabababab

Keluaran

Outputnya adalah seperangkat aturan yang membentuk tata bahasa yang menggambarkan tepat satu kata (input). Setiap nonterminal dilambangkan dengan angka desimal lebih besar dari 9. Simbol awal adalah simbol nomor sepuluh. Contoh output yang sesuai dengan contoh input diberikan di bawah ini; sintaksnya dijelaskan lebih lanjut di bawah ini:

10=11 11 12 12 11 13 13 11 14 14
11=a 12
12=b c
13=a c
14=a b

Setiap aturan memiliki bentuk <nonterminal>=<symbol> <symbol> ...dengan jumlah simbol yang dipisahkan spasi-putih sewenang-wenang di sisi kanan. Setiap output yang mematuhi batasan berikut dan mendapatkan string input dengan benar.

Batasan

Untuk menghentikan orang melakukan hal-hal aneh, sejumlah pembatasan dilakukan:

  • Setiap nonterminal harus muncul setidaknya dua kali di sisi kanan aturan. Misalnya, tata bahasa untuk input abcabcini ilegal karena aturan 12 hanya muncul sekali:

    10=12
    11=a b c
    12=11 11
    
  • Tidak ada urutan dari dua simbol yang berdekatan dapat muncul lebih dari sekali di semua sisi kanan semua aturan, kecuali jika mereka tumpang tindih. Misalnya, tata bahasa untuk input abcabcbcini ilegal karena urutannya bcmuncul dua kali:

    10=11 11 b c
    11=a b c
    

    Tata bahasa yang valid adalah:

    10=11 11 12
    11=a 12
    12=b c
    
  • Program Anda harus berhenti dalam waktu kurang dari satu menit untuk setiap input yang valid yang tidak lebih dari 65535 byte.

  • Seperti biasa, Anda tidak boleh menggunakan fasilitas apa pun dari bahasa Anda atau fungsi perpustakaan apa pun yang membuat solusi sepele atau mengimplementasikan sebagian besar dari itu.

Input sampel

Hasilkan input sampel dengan program C berikut.

#include <stdlib.h>
#include <stdio.h>

int main(int argc, char **argv) {
  unsigned int i,j = 0,k;

  if (argc != 3
     || 2 != sscanf(argv[1],"%u",&i)
      + sscanf(argv[2],"%u",&k)) {
    fprintf(stderr,"Usage: %s seed length\n",argv[0]);
    return EXIT_FAILURE;
  }

  srand(i);

  while(j < k) {
    i = rand() & 0x7f;
    if (i > 34 && i != 127) j++, putchar(i);
  }

  return EXIT_SUCCESS;
}

Input sampel yang dihasilkan oleh program di atas biasanya tidak akan menghasilkan hasil kompresi yang baik. Pertimbangkan untuk menggunakan teks manusia atau kode sumber sebagai input contoh.

Kriteria menang

Ini adalah kode golf; program dengan kode sumber terpendek akan menang. Untuk kredit tambahan, tulis sebuah program yang merekonstruksi input dari output.

FUZxxl
sumber
Ha ha. Saya sudah memiliki beberapa versi dari ini diterapkan (tetapi tidak golf) di Jawa untuk pertanyaan kompleksitas-kolmogorov ...
Peter Taylor
@ PeterTaylor Pertanyaan mana yang tepatnya?
FUZxxl
Itu tidak serta merta menemukan jawaban yang cukup singkat untuk layak diposkan (saya menambahkan strategi pembuatan tata bahasa dan mesin tata bahasa secara perlahan), tetapi skrip inti dalam proyek itu mencobanya di codegolf.stackexchange.com/questions/1682 , codegolf .stackexchange.com / questions / 6043 , codegolf.stackexchange.com/questions/4191 , codegolf.stackexchange.com/questions/4356 dan beberapa komponen pertanyaan lainnya.
Peter Taylor

Jawaban:

3

GolfScript, 111 108 karakter

1/{.}{:^1<{^1$/,2>.{;,)^<.0?)!}*}do-1<.,1>{^1$/[10):10]*0+\+}{;^}if(\}while][0]%.,,]zip{))9+`"="+\~" "*+}%n*

Ini adalah pendekatan yang cukup canggung menggunakan GolfScript. Versi kedua berkinerja lebih baik daripada versi awal. Ini jauh lebih lama daripada kode yang dimaksud tetapi implementasi saya telah membuat do-loop dan ini menyebabkan masalah dengan penerjemah.

Contoh:

> abcba
10=a b c b a

> abcabcbc
10=11 11 12
11=a 12
12=b c

> abcabcbcbcabcacacabcabab
10=11 12 12 13 14 14 c 11 15
11=15 13
12=c b
13=14 b
14=c a
15=a b
Howard
sumber
1

Retraksi - algoritma tidak dapat menangani semua kasus. C, 422 (diperbaiki untuk menghapus dups dalam output, dan menjatuhkan karakter)

Implementasi awal, akan mulai bermain golf itu.

Karena aturan tidak mengharuskannya untuk benar-benar menekan pendekatan naif brute force ini akan dilakukan ...

Dapat memproses panjang 65535 dalam 10 detik

n,m[99999];
c,r[99999][2];

g,i,s,t;

main(){
    for(;(m[n]=getchar())>32;n++);

    while(!g){ // loop until no further changes
        g=1;
        for(s=0;s<n-1;s++) {
            for(t=s+2;t<n-1;t++)if(m[s]==m[t]&&m[s+1]==m[t+1]){
                // create rule
                r[c][0]=m[s];
                r[c++][1]=m[s+1];
                g=0;
                // substitute
                for(i=t=s;i<n;i++){
                    if(m[i]==r[c-1][0]&&m[i+1]==r[c-1][1]){
                        m[t++]=-c;
                        i++;
                    }else
                        m[t++]=m[i];
                }
                n=t;
            }
        }
    }

    for(s=-1;s<c;s++){
        printf("%d=",s+11);
        for(t=0;t<(s<0?n:2);t++){
            i=(s<0?m:r[s])[t];
            i<0?printf("%d ",10-i):printf("%c ",i);
        }
        printf("\n");
    }

}

Contoh dijalankan:

echo abcabcbcbcabcacacabcabab | a.out
10=11 12 13 13 12 14 14 12 12 11 
11=a b 
12=c 11 
13=c b 
14=c a

bayi-kelinci
sumber
Kode Anda tidak berfungsi sesuai dengan spesifikasi. Ini menghasilkan output yang melanggar aturan tidak ada urutan dua karakter dapat muncul dua kali ; pertimbangkan input abcdabcd. Selain itu, kode Anda tampaknya menghapus byte terakhir dari aliran input. Lihat di sini untuk contoh untuk mengamati kedua efek: ideone.com/3Xvtyv
FUZxxl
Juga, output sampel Anda tampaknya salah.
FUZxxl
Anda benar - saya gagal - saya akan melihatnya ketika saya kembali dari kerja: P
baby-kelinci
Itu tidak menghapus byte terakhir dari input untuk saya - dan output sampel saya sudah benar (untuk saya) .. Ayo mainkan "cari bug"!
bayi-kelinci
Output sampel yang Anda posting pasti. Bentuk diperluas dari aturan 10 berakhir dengan aturan 14 yang pada akhirnya berakhir dengan "ca". C terakhir sebenarnya 5 posisi sebelum akhirnya.
FUZxxl