DocumentCode
2533149
Title
Approximate String Matching Using Markovian Distance
Author
Katsumata, Akifumi ; Miura, Takao ; Shioya, Isamu
Author_Institution
Dept. of Electr., Hosei Univ., Tokyo, Japan
fYear
2010
fDate
18-20 Dec. 2010
Firstpage
231
Lastpage
238
Abstract
In this work we examine a new technique for approximate string matching using Markovian distance. Here we assume each character appears in a probabilistic way. By means of this idea, we introduce a notion of dissimilarity using text corpus. Then we propose our sophisticated algorithm based on dynamic programming. We show some experimental results to see how the approach works well.
Keywords
Markov processes; dynamic programming; string matching; text analysis; text editing; Markovian distance; dynamic programming; string matching; text corpus; Algorithm design and analysis; Approximation algorithms; DNA; Hamming distance; Heuristic algorithms; Pattern matching; Semantics; Approximate String Matching; Dynamic programming (DP); Edit Distance; Markovian Distance;
fLanguage
English
Publisher
ieee
Conference_Titel
Parallel Architectures, Algorithms and Programming (PAAP), 2010 Third International Symposium on
Conference_Location
Dalian
Print_ISBN
978-1-4244-9482-8
Type
conf
DOI
10.1109/PAAP.2010.11
Filename
5715088
Link To Document