### Abstract

Lingua originale | English |
---|---|

Pagine | 224-235 |

Numero di pagine | 12 |

Stato di pubblicazione | Published - 2005 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

### Cita questo

*Languages with mismatches and an application to approximate indexing*. 224-235.

**Languages with mismatches and an application to approximate indexing.** / Mignosi, Filippo; Epifanio, Chiara; Gabriele, Alessandra.

Risultato della ricerca: Other

}

TY - CONF

T1 - Languages with mismatches and an application to approximate indexing

AU - Mignosi, Filippo

AU - Epifanio, Chiara

AU - Gabriele, Alessandra

PY - 2005

Y1 - 2005

N2 - In this paper we describe a factorial language, denoted by L(S, k,r), that contains all words that occur in a string 5 up to k mismatches every r symbols. Then we give some combinatorial properties of a parameter, called repetition index and denoted by R(S,k,r), defined as the smallest integer h ? 1 such that all strings of this length occur at most in a unique position of the text S up to k mismatches every r symbols. We prove that R(S, k, r) is a non-increasing function of r and a non-decreasing function of k and that the equation r = R(S, k, r) admits a unique solution. The repetition index plays an important role in the construction of an indexing data structure based on a trie that represents the set of all factors of L(S,k,r) having length equal to R(S,k,r). For each word x ?L(S, k, r) this data structure allows us to find the list occ(x) of all occurrences of the word x in a text S up to k mismatches every r symbols in time proportional to |x| + |occ(x)|.

AB - In this paper we describe a factorial language, denoted by L(S, k,r), that contains all words that occur in a string 5 up to k mismatches every r symbols. Then we give some combinatorial properties of a parameter, called repetition index and denoted by R(S,k,r), defined as the smallest integer h ? 1 such that all strings of this length occur at most in a unique position of the text S up to k mismatches every r symbols. We prove that R(S, k, r) is a non-increasing function of r and a non-decreasing function of k and that the equation r = R(S, k, r) admits a unique solution. The repetition index plays an important role in the construction of an indexing data structure based on a trie that represents the set of all factors of L(S,k,r) having length equal to R(S,k,r). For each word x ?L(S, k, r) this data structure allows us to find the list occ(x) of all occurrences of the word x in a text S up to k mismatches every r symbols in time proportional to |x| + |occ(x)|.

UR - http://hdl.handle.net/10447/28264

M3 - Other

SP - 224

EP - 235

ER -