NDLI: A new string matching algorithm based on logical indexing

Content Provider	IEEE Xplore Digital Library
Author	Kurniawan, D.H. Munir, R.
Copyright Year	2015
Description	Author affiliation: Dept. of Inf., Inst. of Technol., Bandung, Bandung, Indonesia (Kurniawan, D.H.; Munir, R.)
Abstract	Searching process performance is very important in this modern world that consists of various advanced technology. String matching algorithm is one of the most commonly applied algorithms for searching. String that contains sequences of character is the simplest representation of any complex data in our real life, such as search engine database, finger print minutiae, or DNA sequence. The current most famous string algorithms are Knuth-Morris-Pratt (KMP) algorithm and Boyer-Moore (BM) algorithm. Boyer-Moore algorithm and KMP algorithm are not efficient in some cases. We introduced a new variation of string matching algorithm based on Logical-Indexing (LI), which is more efficient than those algorithms. Logical-Indexing algorithm implements a new function or method and defines different jumping rules compared to others. The indexes of texts and patterns are used to reduce the number of comparisons. Index enables us to analyze the condition of comparison without directly comparing each character in the pattern. Theoretically, we have proven that Logical-Indexing algorithm can skip more characters than KMP and BM algorithm by analyzing KMP's and BM's weaknesses then giving the better solution that are implemented in LI. Furthermore, experiments conducted on various combinations of pattern matching cases also demonstrate that the average number of LI's direct comparisons is smaller than KMP's and BM's algorithm.
Starting Page	394
Ending Page	399
File Size	286012
Page Count	6
File Format	PDF
ISBN	9781467367783
ISSN	21556830
e-ISBN	9781467373197
DOI	10.1109/ICEEI.2015.7352533
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-08-10
Publisher Place	Indonesia
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Algorithm design and analysis Electrical engineering paired-character matched-jumping Approximation algorithms margin-jumping full-jumping Indexes Informatics occurrenceTable Pattern matching LI algorithm
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

An offensive algorithm for multi-pattern parameterized string matching

Approximate string matching using phase correlation

Fast parameterized word matching on compressed text

A novel three-phase XML twig pattern matching algorithm based on version tree

New Hashing-Based Multiple String Pattern Matching Algorithms

An Optimizing Chinese String Matching Algorithm Based on the URL Encoding

A new approach for multi-pattern string matching in large text corpora

Pattern Matching with Wildcard Gaps Based on Cross List

New shift table algorithm for multiple variable length string pattern matching

A new string matching algorithm based on logical indexing

Similar Documents

An offensive algorithm for multi-pattern parameterized string matching

Approximate string matching using phase correlation

Fast parameterized word matching on compressed text

A novel three-phase XML twig pattern matching algorithm based on version tree

New Hashing-Based Multiple String Pattern Matching Algorithms

An Optimizing Chinese String Matching Algorithm Based on the URL Encoding

A new approach for multi-pattern string matching in large text corpora

Pattern Matching with Wildcard Gaps Based on Cross List

New shift table algorithm for multiple variable length string pattern matching

A new string matching algorithm based on logical indexing