Dataset Information

A new split based searching for exact pattern matching for natural texts.

ABSTRACT: Exact pattern matching algorithms are popular and used widely in several applications, such as molecular biology, text processing, image processing, web search engines, network intrusion detection systems and operating systems. The focus of these algorithms is to achieve time efficiency according to applications but not memory consumption. In this work, we propose a novel idea to achieve both time efficiency and memory consumption by splitting query string for searching in Corpus. For a given text, the proposed algorithm split the query pattern into two equal halves and considers the second (right) half as a query string for searching in Corpus. Once the match is found with second halves, the proposed algorithm applies brute force procedure to find remaining match by referring the location of right half. Experimental results on different S1 Dataset, namely Arabic, English, Chinese, Italian and French text databases show that the proposed algorithm outperforms the existing S1 Algorithm in terms of time efficiency and memory consumption as the length of the query pattern increases.

SUBMITTER: Hakak S

PROVIDER: S-EPMC6062031 | biostudies-literature | 2018

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

A new split based searching for exact pattern matching for natural texts.

Hakak Saqib S Hakak Saqib S Kamsin Amirrudin A Shivakumara Palaiahnakote P Idna Idris Mohd Yamani MY Gilkar Gulshan Amin GA

PloS one 20180726 7

Exact pattern matching algorithms are popular and used widely in several applications, such as molecular biology, text processing, image processing, web search engines, network intrusion detection systems and operating systems. The focus of these algorithms is to achieve time efficiency according to applications but not memory consumption. In this work, we propose a novel idea to achieve both time efficiency and memory consumption by splitting query string for searching in Corpus. For a given te ...[more]

PMID: 30048486

Similar Datasets

Project description:The string-matching paradigm is applied in every computer science and science branch in general. The existence of a plethora of string-matching algorithms makes it hard to choose the best one for any particular case. Expressing, measuring, and testing algorithm efficiency is a challenging task with many potential pitfalls. Algorithm efficiency can be measured based on the usage of different resources. In software engineering, algorithmic productivity is a property of an algorithm execution identified with the computational resources the algorithm consumes. Resource usage in algorithm execution could be determined, and for maximum efficiency, the goal is to minimize resource usage. Guided by the fact that standard measures of algorithm efficiency, such as execution time, directly depend on the number of executed actions. Without touching the problematics of computer power consumption or memory, which also depends on the algorithm type and the techniques used in algorithm development, we have developed a methodology which enables the researchers to choose an efficient algorithm for a specific domain. String searching algorithms efficiency is usually observed independently from the domain texts being searched. This research paper aims to present the idea that algorithm efficiency depends on the properties of searched string and properties of the texts being searched, accompanied by the theoretical analysis of the proposed approach. In the proposed methodology, algorithm efficiency is expressed through character comparison count metrics. The character comparison count metrics is a formal quantitative measure independent of algorithm implementation subtleties and computer platform differences. The model is developed for a particular problem domain by using appropriate domain data (patterns and texts) and provides for a specific domain the ranking of algorithms according to the patterns' entropy. The proposed approach is limited to on-line exact string-matching problems based on information entropy for a search pattern. Meticulous empirical testing depicts the methodology implementation and purports soundness of the methodology.

Project description:This article presents efficient quantum solutions for exact multiple pattern matching to process the biological sequences. The classical solution takes Ο(mN) time for matching m patterns over N sized text database. The quantum search mechanism is a core for pattern matching, as this reduces time complexity and achieves computational speedup. Few quantum methods are available for multiple pattern matching, which executes search oracle for each pattern in successive iterations. Such solutions are likely acceptable because of classical equivalent quantum designs. However, these methods are constrained with the inclusion of multiplicative factor m in their complexities. An optimal quantum design is to execute multiple search oracle in parallel on the quantum processing unit with a single-core that completely removes the multiplicative factor m, however, this method is impractical to design. We have no effective quantum solutions to process multiple patterns at present. Therefore, we propose quantum algorithms using quantum processing unit with C quantum cores working on shared quantum memory. This quantum parallel design would be effective for searching all t exact occurrences of each pattern. To our knowledge, no attempts have been made to design multiple pattern matching algorithms on quantum multicore processor. Thus, some quantum remarkable exact single pattern matching algorithms are enhanced here with their equivalent versions, namely enhanced quantum memory processing based exact algorithm and enhanced quantum-based combined exact algorithm for multiple pattern matching. Our quantum solutions find all t exact occurrences of each pattern inside the biological sequence in O((m/C)N) and O((m/C)t) time complexities. This article shows the hybrid simulation of quantum algorithms to validate quantum solutions. Our theoretical-experimental results justify the significant improvements that these algorithms outperform over the existing classical solutions and are proven effective in quantum counterparts.

Project description:BackgroundMore so than face-to-face counseling, users of online text-based services might drop out from a session before establishing a clear closure or expressing the intention to leave. Such premature departure may be indicative of heightened risk or dissatisfaction with the service or counselor. However, there is no systematic way to identify this understudied phenomenon.PurposeThis study has two objectives. First, we developed a set of rules and used logic-based pattern matching techniques to systematically identify premature departures in an online text-based counseling service. Second, we validated the importance of premature departure by examining its association with user satisfaction. We hypothesized that the users who rated the session as less helpful were more likely to have departed prematurely.MethodWe developed and tested a classification model using a sample of 575 human-annotated sessions from an online text-based counseling platform. We used 80% of the dataset to train and develop the model and 20% of the dataset to evaluate the model performance. We further applied the model to the full dataset (34,821 sessions). We compared user satisfaction between premature departure and completed sessions based on data from a post-session survey.ResultsThe resulting model achieved 97% and 92% F1 score in detecting premature departure cases in the training and test sets, respectively, suggesting it is highly consistent with the judgment of human coders. When applied to the full dataset, the model classified 15,150 (43.5%) sessions as premature departure and the remaining 19,671 (56.5%) as completed sessions. Completed cases (15.2%) were more likely to fill the post-chat survey than premature departure cases (4.0%). Premature departure was significantly associated with lower perceived helpfulness and effectiveness in distress reduction.ConclusionsThe model is the first that systematically and accurately identifies premature departure in online text-based counseling. It can be readily modified and transferred to other contexts for the purpose of risk mitigation and service evaluation and improvement.

Dataset Information

A new split based searching for exact pattern matching for natural texts.

Publications

A new split based searching for exact pattern matching for natural texts.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets