Quali sono i buoni casi di test per gli algoritmi di ricerca delle sottostringhe di benchmarking e stress test?

Question

Sto provando a valutare diversi algoritmi e implementazioni di ricerca sottostringa (ala strstr) e cerco alcune stringhe di ago e pagliaio ben fatte che cattureranno le prestazioni del caso peggiore e possibili bug di casi d'angolo. Suppongo di poterli risolvere da solo ma immagino che qualcuno debba avere una buona collezione di casi di prova seduti da qualche parte ...

Answer 1

Non risponde direttamente alla tua domanda, ma potresti trovare gli algoritmi nel libro - Algoritmi su stringhe, alberi e sequenze: informatica e biologia computazionale - interessante (ha molti nuovi algoritmi sulla ricerca sotto stringa). Inoltre, è anche una buona fonte di casi speciali e complessi.

Answer 2

Alcuni pensieri e una risposta parziale a me stesso:

caso peggiore per l'algoritmo a forza bruta:

a^(n+1) b in (a^n b)^m

esempio aaab in aabaabaabaabaabaabaab

caso peggiore per SMOA:

Qualcosa di simile yxyxyxxyxyxyxx in (yxyxyxxyxyxyxy)^n. Ha bisogno di ulteriore raffinamento. Sto cercando di garantire che ogni avanzamento sia solo la metà della lunghezza della corrispondenza parziale e che il calcolo del suffisso massimale richieda la massima quantità di backtracking. Sono abbastanza sicuro di essere sulla strada giusta perché questo tipo di caso è l'unico modo che ho trovato finora per rendere la mia implementazione di SMOA (che è asintoticamente 6n+5) più lenta rispetto a Two-Way di glibc (che è asintoticamente 2n-m ma ha un overhead di preelaborazione moderatamente doloroso).

caso peggiore per nulla al rotolamento hash basato:

Qualunque sia la sequenza di byte provoca collisioni hash con l'hash dell'ago. Per ogni hash ragionevolmente veloce e un determinato ago, dovrebbe essere facile costruire un pagliaio il cui hash si scontra con l'hash dell'ago in ogni punto. Tuttavia, sembra difficile creare contemporaneamente corrispondenze parziali lunghe, che sono l'unico modo per ottenere il comportamento del caso peggiore. Naturalmente, nel caso peggiore, l'ago deve avere una certa periodicità e un modo per emulare l'hash regolando solo i caratteri finali.

caso peggiore per bidirezionale:

sembra essere molto breve ago con non banale decomposizione MS - qualcosa come bac - dove il pagliaio contiene ripetuto falsi positivi nel componente metà destra dell'ago - qualcosa come dacdacdacdacdacdacdac . L'unico modo in cui questo algoritmo può essere lento (oltre che dagli autori di glibc che lo implementano male ...) è quello di rendere il ciclo esterno iterativo molte volte e ripetutamente di sostenere tale overhead (e di rendere significativo il sovraccarico di installazione).

Altri algoritmi:

sono davvero interessati solo gli algoritmi che sono O(1) nello spazio e hanno basso overhead di pre-elaborazione, quindi non hanno guardato i loro casi peggiori così tanto. Almeno Boyer-Moore (senza le modifiche per renderlo O(n)) ha un caso peggiore non banale dove diventa O(nm).

Answer 3

Una procedura che potrebbe dare statistiche interessanti, anche se non ho tempo per testare questo momento:

Randomize sopra la lunghezza della stringa, poi randomizzare sui contenuti della stringa di quella lunghezza, quindi rendere casuale nel corso di offset/lunghezza di un sottostringa (possibilmente qualcosa non nella stringa), quindi clobber casualmente sulla sottostringa (possibilmente non del tutto), ripetizione .

Answer 4

È possibile generare stringhe di container (Resp., Conteneva valori di test) in modo ricorsivo da:

partire con la stringa vuota, genera tutte le stringhe fornite dal l'aumento di una stringa attualmente nel set con l'aggiunta di un personaggio di un alfabeto a sinistra oa destra (entrambi).

L'alfabeto per generare stringhe di contenitori è scelto da voi.

Test 2 alfabeti per stringhe contenute. Uno è quello che compone le stringhe del contenitore, l'altro è il suo complemento.