Open AccessCombination of levenshtein distance and rabin-karp to improve the accuracy of document equivalence level
Author(s) -
Andysah Putera Utama Siahaan,
Solly Aryza,
Eko Hariyanto,
. Rusiadi,
Andre Hasudungan Lubis,
Ali Ikhwan,
Phak Len Eh Kan
Publication year - 2018
Publication title -
international journal of engineering and technology
Language(s) - English
Resource type - Journals
ISSN - 2227-524X
DOI - 10.14419/ijet.v7i2.27.12084
Subject(s) - hash function , levenshtein distance , substring , computer science , perfect hash function , hash table , algorithm , theoretical computer science , data structure , computer security , programming language
Rabin Karp algorithm is a search algorithm that searches for a substring pattern in a text using hashing. It is beneficial for matching words with many patterns. One of the practical applications of Rabin Karp's algorithm is in the detection of plagiarism. Michael O. Rabin and Richard M. Karp invented the algorithm. This algorithm performs string search by using a hash function. A hash function is the values that are compared between two documents to determine the level of similarity of the document. Rabin-Karp algorithm is not very good for single pattern text search. This algorithm is perfect for multiple pattern search. The Levenshtein algorithm can be used to replace the hash calculation on the Rabin-Karp algorithm. The hash calculation on Rabin-Karp only counts the number of hashes that have the same value in both documents. Using the Levenshtein algorithm, the calculation of the hash distance in both documents will result in better accuracy.