Keskustelu: Yleinen keskustelu: Toistuva data

Minulla on taulukko, jonka riveistä minun pitäisi saada löydettyä toistuvat kaavat. Mikähän olisi paras algoritmi / tapa tähän.

1
2
3
1
2
3
1
2
3

Yllä olevasta taulukosta tulokseksi tulisi siis 1, 2, 3 (koska se toistuu kolmesti). Kuitenkin jos viimeisenä ylläolevassa taulukossa olisi esim. numero 4, niin tulos olisi 1,2,3,1,2,3,1,2,3,4.

Oma taulukkoni on tekstidataa ja tekstejä on neljää erilaista. Mistään hirveän suuresta systeemistä ei ole kyse, sillä vaikka toistuvuuksia löytyisikin isommilta alueilta, niin ne on turhia jos rivejä on useampi kuin ~50.

Pitääkö jakson siis toistua koko taulukon alusta loppuun? Silloin yksinkertaisinta (mutta toki hidasta) olisi käydä läpi kaikki mahdolliset pituudet 1–N, tarkistaa jakojäännöksellä, että datan pituus menee tällä tasan, ja käydä sitten silmukassa läpi data ja katsoa, että jokainen arvo on sama kuin aiemmin. C++-toteutus toimisi suunnilleen näin:

int data[N];
for (int J = 1; J <= N; ++J) {
  if (N % J != 0) continue;
  bool ok = true;
  for (int i = J; i < N; ++i) {
    if (data[i] != data[i - J]) {
      ok = false;
      break;
    }
  }
  if (ok) {
    // J arvon sarja toistuu.
  }
}

Jos rivejä ei ole paljon, yllä oleva suoraviivainen algoritmi on varmasti riittävä. Merkkijonojen tutkimuksessa vastaava ongelma on etsiä merkkijonon jakso (period of a string), ja tehokkaampia algoritmeja on olemassa.