Log in

Relevant bibliographies by topics / String algorithm / Journal articles

Journal articles on the topic 'String algorithm'

To see the other types of publications on this topic, follow the link: String algorithm.

Author: Grafiati

Published: 9 March 2023

Last updated: 10 March 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'String algorithm.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Bhagya Sri, Mukku, Rachita Bhavsar, and Preeti Narooka. "String Matching Algorithms." International Journal Of Engineering And Computer Science 7, no. 03 (March 23, 2018): 23769–72. http://dx.doi.org/10.18535/ijecs/v7i3.19.

Full text

Abstract:

To analyze the content of the documents, the various pattern matching algorithms are used to find all the occurrences of a limited set of patterns within an input text or input document. In order to perform this task, this research work used four existing string matching algorithms; they are Brute Force algorithm, Knuth-Morris-Pratt algorithm (KMP), Boyer Moore algorithm and Rabin Karp algorithm. This work also proposes three new string matching algorithms. They are Enhanced Boyer Moore algorithm, Enhanced Rabin Karp algorithm and Enhanced Knuth-Morris-Pratt algorithm. Findings: For experimentation, this work has used two types of documents, i.e. .txt and .docx. Performance measures used are search time, number of iterations and accuracy. From the experimental results, it is realized that the enhanced KMP algorithm gives better accuracy compared to other string matching algorithms. Application/Improvements: Normally, these algorithms are used in the field of text mining, document classification, content analysis and plagiarism detection. In future, these algorithms have to be enhanced to improve their performance and the various types of documents will be used for experimentation.

APA, Harvard, Vancouver, ISO, and other styles

2

Zhang, Zhaoyang. "Review on String-Matching Algorithm." SHS Web of Conferences 144 (2022): 03018. http://dx.doi.org/10.1051/shsconf/202214403018.

Full text

Abstract:

String-matching algorithm is one of the most researched algorithms in computer science which has become an important factor in many technologies. This field aims at utilizing the least time and resources to find desired sequence of character in complex data content. The most classical and famous string-search algorithms are Knuth-Morris-Pratt (KMP) algorithm and Boyer-Moore (DM) algorithm. These two algorithms provide efficient heuristic jump rules by prefix or suffix. Bitap algorithm was the first to introduce bit-parallelism into string-matching field. Backward Non-Deterministic DAWG Matching (BNDM) algorithm is a modern practical algorithm that is an outstanding combination of theoretical research and practical application. Those meaningful algorithms play a guiding role in future research in string-search algorithm to improve the average performance of the algorithm and reduce resource consumption.

APA, Harvard, Vancouver, ISO, and other styles

3

Russo, Luıs, and Alexandre Francisco. "Small Longest Tandem Scattered Subsequences." Scientific Annals of Computer Science 31, no. 1 (August 9, 2021): 79–110. http://dx.doi.org/10.7561/sacs.2021.1.79.

Full text

Abstract:

We consider the problem of identifying tandem scattered subsequences within a string. Our algorithm identifies a longest subsequence which occurs twice without overlap in a string. This algorithm is based on the Hunt-Szymanski algorithm, therefore its performance improves if the string is not self similar, which occurs naturally on strings over large alphabets. Our algorithm relies on new results for data structures that support dynamic longest increasing sub-sequences. In the process we also obtain improved algorithms for the decremental string comparison problem.

APA, Harvard, Vancouver, ISO, and other styles

4

Jantan, Hamidah, and Nurul Aisyiah Baharudin. "Mobile-Based Word Matching Detection using Intelligent Predictive Algorithm." International Journal of Interactive Mobile Technologies (iJIM) 13, no. 09 (September 5, 2019): 140. http://dx.doi.org/10.3991/ijim.v13i09.10848.

Full text

Abstract:

Word matching is a string searching technique for information retrieval in Natural Language Processing (NLP). There are several algorithms have been used for string search and matching such as Knuth Morris Pratt, Boyer Moore, Horspool, Intelligent Predictive and many other. However, there some issues need to be considered in measuring the performance of the algorithms such as the efficiency for searching small alphabets, time taken in processing the pattern of the text and extra space to support a huge table or state machines. Intelligent Predictive (IP) algorithm capable to solve several word matching issues discovered in other string searching algorithms especially with abilities to skip the pre-processing of the pattern, uses simple rules during matching process and does not involved complex computations. Due to those reasons,<strong> </strong>IP algorithm is used in this study due to the ability of this algorithm to produce a good result in string searching process. This article aims to apply IP algorithm together with Optical Character Recognition (OCR) tool for mobile-based word matching detection. There are four phases in this study consists of data preparation, mobile based system design, algorithm implementation and result analysis. The efficiency of the proposed algorithm was evaluated based on the execution time of searching process among the selected algorithms. The result shows that the IP algorithm for string searching process is more efficient in execution time compared to well-known algorithm i.e. Boyer Moore algorithm. In future work, the performance of string searching process can be enhanced by using other suitable optimization searching techniques such as Genetic Algorithm, Particle Swarm Optimization, Ant Colony Optimization and many others.

APA, Harvard, Vancouver, ISO, and other styles

5

Khadiev, Kamil, Artem Ilikaev, and Jevgenijs Vihrovs. "Quantum Algorithms for Some Strings Problems Based on Quantum String Comparator." Mathematics 10, no. 3 (January 26, 2022): 377. http://dx.doi.org/10.3390/math10030377.

Full text

Abstract:

We study algorithms for solving three problems on strings. These are sorting of n strings of length k, “the Most Frequent String Search Problem”, and “searching intersection of two sequences of strings”. We construct quantum algorithms that are faster than classical (randomized or deterministic) counterparts for each of these problems. The quantum algorithms are based on the quantum procedure for comparing two strings of length k in O(k) queries. The first problem is sorting n strings of length k. We show that classical complexity of the problem is Θ(nk) for constant size alphabet, but our quantum algorithm has O˜(nk) complexity. The second one is searching the most frequent string among n strings of length k. We show that the classical complexity of the problem is Θ(nk), but our quantum algorithm has O˜(nk) complexity. The third problem is searching for an intersection of two sequences of strings. All strings have the same length k. The size of the first set is n, and the size of the second set is m. We show that the classical complexity of the problem is Θ((n+m)k), but our quantum algorithm has O˜((n+m)k) complexity.

APA, Harvard, Vancouver, ISO, and other styles

6

Franek, Frantisek, and Michael Liut. "Computing Maximal Lyndon Substrings of a String." Algorithms 13, no. 11 (November 12, 2020): 294. http://dx.doi.org/10.3390/a13110294.

Full text

Abstract:

There are two reasons to have an efficient algorithm for identifying all right-maximal Lyndon substrings of a string: firstly, Bannai et al. introduced in 2015 a linear algorithm to compute all runs of a string that relies on knowing all right-maximal Lyndon substrings of the input string, and secondly, Franek et al. showed in 2017 a linear equivalence of sorting suffixes and sorting right-maximal Lyndon substrings of a string, inspired by a novel suffix sorting algorithm of Baier. In 2016, Franek et al. presented a brief overview of algorithms for computing the Lyndon array that encodes the knowledge of right-maximal Lyndon substrings of the input string. Among those presented were two well-known algorithms for computing the Lyndon array: a quadratic in-place algorithm based on the iterated Duval algorithm for Lyndon factorization and a linear algorithmic scheme based on linear suffix sorting, computing the inverse suffix array, and applying to it the next smaller value algorithm. Duval’s algorithm works for strings over any ordered alphabet, while for linear suffix sorting, a constant or an integer alphabet is required. The authors at that time were not aware of Baier’s algorithm. In 2017, our research group proposed a novel algorithm for the Lyndon array. Though the proposed algorithm is linear in the average case and has O(nlog(n)) worst-case complexity, it is interesting as it emulates the fast Fourier algorithm’s recursive approach and introduces τ-reduction, which might be of independent interest. In 2018, we presented a linear algorithm to compute the Lyndon array of a string inspired by Phase I of Baier’s algorithm for suffix sorting. This paper presents the theoretical analysis of these two algorithms and provides empirical comparisons of both of their C++ implementations with respect to the iterated Duval algorithm.

APA, Harvard, Vancouver, ISO, and other styles

7

Tsarev, Roman Yu, Elena A. Tsareva, and Alexey S. Chernigovskiy. "Combined String Searching Algorithm." Journal of Siberian Federal University. Engineering & Technologies 10, no. 1 (February 2017): 126–35. http://dx.doi.org/10.17516/1999-494x-2017-10-1-126-135.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Subada, Mhd Ali. "Comparisonal Analysis Of Even-Rodeh Algorithm Code And Fibonacci Code Algorithm For Text File Compression." Journal Basic Science and Technology 11, no. 1 (February 28, 2022): 1–7. http://dx.doi.org/10.35335/jbst.v11i1.1765.

Full text

Abstract:

The growing requirement towards bigger storage space is the main cause of new compression techniques being developed. By doing compression, big chunks of data will be lowered in size to save storage space. In this research we will be using the Even-Rodeh Code and Fibonacci Code Algorithm, the performance will be benchmarked with bitrate, compression ratio, space saving, compression and decompression time in text files. Compression is done by reading strings on text files, and then the Even-Rodeh Code and Fibonacci Code Algorithm makes a string code and performs compression. The compression results are *.erc and *.fib files containing character information and string bit which can be decompressed. The decompression result is the original text file which can be saved using the extensions *.doc, *.docx, *.pdf. In this system test the sample used are strings that contains one type of character (Homogen String) and strings that contain several types of character (heterogeneous string) saved in text files *.doc,*.docx, *.pdf. In homogeneous string compressions we can observe that the Fibonacci Code is more efficient in compression ratio, averaging at 0.25 and faster decompression time at 0.011 millisecond average compared to the Even-Rodeh Code Algorithm. In heterogeneous string compression the Fibonacci Code performs better than the Even-Rodeh Code on an average compression ratio of 0.65 and a shorter average decompression time of 0.293 milliseconds.

APA, Harvard, Vancouver, ISO, and other styles

9

Ghuman, Sukhpal, Emanuele Giaquinta, and Jorma Tarhio. "Lyndon Factorization Algorithms for Small Alphabets and Run-Length Encoded Strings." Algorithms 12, no. 6 (June 21, 2019): 124. http://dx.doi.org/10.3390/a12060124.

Full text

Abstract:

We present two modifications of Duval’s algorithm for computing the Lyndon factorization of a string. One of the algorithms has been designed for strings containing runs of the smallest character. It works best for small alphabets and it is able to skip a significant number of characters of the string. Moreover, it can be engineered to have linear time complexity in the worst case. When there is a run-length encoded string R of length ρ , the other algorithm computes the Lyndon factorization of R in O ( ρ ) time and in constant space. It is shown by experimental results that the new variations are faster than Duval’s original algorithm in many scenarios.

APA, Harvard, Vancouver, ISO, and other styles

10

Markić, Ivan, Maja Štula, Marija Zorić, and Darko Stipaničev. "Entropy-Based Approach in Selection Exact String-Matching Algorithms." Entropy 23, no. 1 (December 28, 2020): 31. http://dx.doi.org/10.3390/e23010031.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

11

Baturu, Charles, and Naufal abdi. "Brute Force Algorithm Implementation Of Dictionary Search." Jurnal Info Sains : Informatika dan Sains 10, no. 1 (March 1, 2020): 24–30. http://dx.doi.org/10.54209/infosains.v10i1.29.

Full text

Abstract:

In the manual dictionary the more words are accommodated, the heavier the dictionary. Dictionaries that are generally book-shaped are difficult to carry anywhere because they are thick and heavy. With this mobile-based computer dictionary application, users no longer need to carry heavy dictionaries and the search process will also be faster and easier. This mobile-based kmputer dictionary application is created using the java programming language with the NetBeans 7.0 editor and using an RMS (Record Management System) based database. So it can be installed on various types of mobile phones that already support Java. String Matching is one of the algorithms used to speed up the search process for the desired word. String matching algorithms have been used frequently before as examples in the process of matching strings based on the equation of text data namely Brute Force. Because this Brute Force algorithm can be used to perform string or text searches. Brute force algorithm is an algorithm to match a pattern with all text between 0 and n-m to find the presence of a pattern in text.

APA, Harvard, Vancouver, ISO, and other styles

12

Ali, Rawan. "An Algorithm for String Searching." International Journal of Computer Applications 177, no. 10 (October 17, 2019): 17–22. http://dx.doi.org/10.5120/ijca2019919484.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Atheer Akram AbdulRazzaq, NurAini Abdul Rashid, and Aziz Nasser Boraik Ali. "Fast Hybrid String Matching Algorithm." International Journal of Digital Content Technology and its Applications 7, no. 10 (June 30, 2013): 62–71. http://dx.doi.org/10.4156/jdcta.vol7.issue10.7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Ahmed, Mustaq, M. Kaykobad, and Rezaul Alam Chowdhury. "A New String Matching Algorithm." International Journal of Computer Mathematics 80, no. 7 (July 2003): 825–34. http://dx.doi.org/10.1080/0020716031000087113.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Takefuji, Y., T. Tanaka, and K. C. Lee. "A parallel string search algorithm." IEEE Transactions on Systems, Man, and Cybernetics 22, no. 2 (1992): 332–36. http://dx.doi.org/10.1109/21.148407.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Gurung, Dipendra, Udit Kr Chakraborty, and Pratikshya Sharma. "Intelligent Predictive String Search Algorithm." Procedia Computer Science 79 (2016): 161–69. http://dx.doi.org/10.1016/j.procs.2016.03.116.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Hancart, Christophe. "On Simon's string searching algorithm." Information Processing Letters 47, no. 2 (August 1993): 95–99. http://dx.doi.org/10.1016/0020-0190(93)90231-w.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Allauzen, Cyril, and Mathieu Raffinot. "Simple Optimal String Matching Algorithm." Journal of Algorithms 36, no. 1 (July 2000): 102–16. http://dx.doi.org/10.1006/jagm.2000.1087.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Yang, Q. X., S. S. Yuan, L. Zhao, L. Chun, and S. Peng. "Faster algorithm of string comparison." Pattern Analysis & Applications 6, no. 2 (June 1, 2003): 122–33. http://dx.doi.org/10.1007/s10044-002-0180-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Chang, Daniel K. "A string pattern—matching algorithm." Journal of Systems and Software 22, no. 3 (September 1993): 207–16. http://dx.doi.org/10.1016/0164-1212(93)90111-a.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Kim, Jong Yong, and John Shawe-Taylor. "An approximate string-matching algorithm." Theoretical Computer Science 92, no. 1 (January 1992): 107–17. http://dx.doi.org/10.1016/0304-3975(92)90138-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Jiang, Ya Ping, Yue Xia Tian, and Jun Wei Zhao. "An Improved BMQ Algorithm for Pattern Matching." Advanced Materials Research 998-999 (July 2014): 814–17. http://dx.doi.org/10.4028/www.scientific.net/amr.998-999.814.

Full text

Abstract:

Pattern matching algorithm is widely used. It plays an important role in information retrieval, data mining, intrusion detection and other fields. Among them, the BM algorithm is the most common. A new improved algorithm-BMQ algorithm is proposed on the basis of BM and related algorithms. The improved algorithm makes use of uniqueness and combination of the last character and next character of string, to increase the probability of the maximum right shift. Theoretical analysis and experimental comparison shows that the BMQ is better than BM algorithms in the process of string matching and string searching; in order to further verify its effectiveness, the improved algorithm is introduced to intrusion detection system, the experimental results show that BMQ algorithm improves the efficiency of intrusion detection.

APA, Harvard, Vancouver, ISO, and other styles

23

Khadiev, Kamil, and Vladislav Remidovskii. "Classical and Quantum Algorithms for Assembling a Text from a Dictionary." Nonlinear Phenomena in Complex Systems 24, no. 3 (October 12, 2021): 207–21. http://dx.doi.org/10.33581/1561-4085-2021-24-3-207-221.

Full text

Abstract:

We study algorithms for solving the problem of assembling a text (long string) from a dictionary (a sequence of small strings). The problem has an application in bioinformatics and has a connection with the sequence assembly method for reconstructing a long deoxyribonucleic-acid (DNA) sequence from small fragments. The problem is assembling a string t of length n from strings s1,...,sm. Firstly, we provide a classical (randomized) algorithm with running time Õ(nL0.5 + L) where L is the sum of lengths of s1,...,sm. Secondly, we provide a quantum algorithm with running time Õ(nL0.25 + √mL). Thirdly, we show the lower bound for a classical (randomized or deterministic) algorithm that is Ω(n+L). So, we obtain the quadratic quantum speed-up with respect to the parameter L; and our quantum algorithm have smaller running time comparing to any classical (randomized or deterministic) algorithm in the case of non-constant length of strings in the dictionary.

APA, Harvard, Vancouver, ISO, and other styles

24

Fadlil, Abdul, Sunardi Sunardi, and Rezki Ramdhani. "Similarity Identification Based on Word Trigrams Using Exact String Matching Algorithms." INTENSIF: Jurnal Ilmiah Penelitian dan Penerapan Teknologi Sistem Informasi 6, no. 2 (August 13, 2022): 253–70. http://dx.doi.org/10.29407/intensif.v6i2.18141.

Full text

Abstract:

Several studies regarding excellent exact string matching algorithms can be used to identify similarity, including the Rabin-Karp, Winnowing, and Horspool Boyer-Moore algorithms. In determining similarities, the Rabin-Karp and Winnowing algorithms use fingerprints, while the Horspool Boyer-Moore algorithm uses a bad-character table. However, previous research focused on identifying similarities using these algorithms based on character n-gram. In contrast, identification based on the word n-gram to determine the similarity based on its linguistic meaning, especially for longer strings, had not been covered yet. Therefore, a word-level trigram was proposed to identify similarities based on the word trigrams using the three algorithms and compare each performance. Based on precision, recall, and running time comparison, the Rabin-Karp algorithm results were 100%, 100%, and 0.19 ms, respectively; the Winnowing algorithm results with the smallest window were 100%, 56%, and 0.18 ms, respectively; and the Horspool algorithm results were 100%, 100%, and 0.06 ms. From these results, it can be concluded that the performance of the Horspool Boyer-Moore algorithm is better in terms of precision, recall, and running time.

APA, Harvard, Vancouver, ISO, and other styles

25

Al-Ssulami, Abdulrakeeb M., Hassan Mathkour, and Mohammed Amer Arafah. "Efficient String Matching Algorithm for Searching Large DNA and Binary Texts." International Journal on Semantic Web and Information Systems 13, no. 4 (October 2017): 198–220. http://dx.doi.org/10.4018/ijswis.2017100110.

Full text

Abstract:

The exact string matching is essential in application areas such as Bioinformatics and Intrusion Detection Systems. Speeding-up the string matching algorithm will therefore result in accelerating the searching process in DNA and binary data. Previously, there are two types of fast algorithms exist, bit-parallel based algorithms and hashing algorithms. The bit-parallel based are efficient when dealing with patterns of short lengths, less than 64, but slow on long patterns. On the other hand, hashing algorithms have optimal sublinear average case on large alphabets and long patterns, but the efficiency not so good on small alphabet such as DNA and binary texts. In this paper, the authors present hybrid algorithm to overcome the shortcomings of those previous algorithms. The proposed algorithm is based on q-gram hashing with guaranteeing the maximal shift in advance. Experimental results on random and complete human genome confirm that the proposed algorithm is efficient on various pattern lengths and small alphabet.

APA, Harvard, Vancouver, ISO, and other styles

26

FARO, SIMONE, and THIERRY LECROQ. "EFFICIENT VARIANTS OF THE BACKWARD-ORACLE-MATCHING ALGORITHM." International Journal of Foundations of Computer Science 20, no. 06 (December 2009): 967–84. http://dx.doi.org/10.1142/s0129054109006991.

Full text

Abstract:

In this article we present two efficient variants of the BOM string matching algorithm which are more efficient and flexible than the original algorithm. We also present bit-parallel versions of them obtaining an efficient variant of the BNDM algorithm. Then we compare the newly presented algorithms with some of the most recent and effective string matching algorithms. It turns out that the new proposed variants are very flexible and achieve very good results, especially in the case of large alphabets.

APA, Harvard, Vancouver, ISO, and other styles

27

Rajashekharaiah, K. M. M. "Parallel String Matching Algorithm Using Grid." International Journal of Distributed and Parallel systems 3, no. 3 (May 31, 2012): 21–28. http://dx.doi.org/10.5121/ijdps.2012.3303.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Ejendibia, Preye, and Barileé B. "String Searching with DFA-based Algorithm." International Journal of Applied Information Systems 9, no. 8 (October 5, 2015): 1–6. http://dx.doi.org/10.5120/ijais2015451415.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Gouda, Karam, and Metwally Rashad. "Efficient String Edit Similarity Join Algorithm." Computing and Informatics 36, no. 3 (2017): 683–704. http://dx.doi.org/10.4149/cai_2017_3_683.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Mhashi, Mahmoud, Adnan Rawashdeh, and Awni Hammouri. "A Fast Approximate String Searching Algorithm." Journal of Computer Science 1, no. 3 (March 1, 2005): 405–12. http://dx.doi.org/10.3844/jcssp.2005.405.412.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

LU, SHIYONG, FENG CAO, and YI LU. "PAMA: A FAST STRING MATCHING ALGORITHM." International Journal of Foundations of Computer Science 17, no. 02 (April 2006): 357–78. http://dx.doi.org/10.1142/s0129054106003875.

Full text

Abstract:

String matching is a fundamental operation in computer science, and its performance has great impact on many applications including database query, text processing, DNA and protein sequence analysis. In this paper, we propose a fast string matching algorithm, PAMA (PAttern MAtching). The shift rule used by PAMA not only subsumes both the bad character rule and the good suffix rule employed by the well-known Boyer-Moore algorithm, but also employs an additional key observation to enable faster shifting during the string matching process. Theoretically, we prove that from the same alignment, the next shift of PAMA will be at least as much as that of the Boyer-Moore algorithm. Experimentally, we show that PAMA indeed significantly outperforms the original Boyer-Moore algorithm in almost all cases, and outperforms other Boyer-Moore variants such as Tuned-BM, Turbo-BM and Horspool for long patterns (length ≥ 128) or for small alphabets (size < 8).

APA, Harvard, Vancouver, ISO, and other styles

32

He, Longtao, Binxing Fang, and Jie Sui. "The wide window string matching algorithm." Theoretical Computer Science 332, no. 1-3 (February 2005): 391–404. http://dx.doi.org/10.1016/j.tcs.2004.12.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Liu, Z., X. Du, and N. Ishi. "An improved adaptive string searching algorithm." Software: Practice and Experience 28, no. 2 (February 1998): 191–98. http://dx.doi.org/10.1002/(sici)1097-024x(199802)28:2<191::aid-spe149>3.0.co;2-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Lasch, Robert, Ismail Oukid, Roman Dementiev, Norman May, Suleyman S. Demirsoy, and Kai-Uwe Sattler. "Faster & strong: string dictionary compression using sampling and fast vectorized decompression." VLDB Journal 29, no. 6 (July 20, 2020): 1263–85. http://dx.doi.org/10.1007/s00778-020-00620-x.

Full text

Abstract:

AbstractString dictionaries constitute a large portion of the memory footprint of database applications. While strong string dictionary compression algorithms exist, these come with impractical access and compression times. Therefore, lightweight algorithms such as front coding (PFC) are favored in practice. This paper endeavors to make strong string dictionary compression practical. We focus on Re-Pair Front Coding (RPFC), a grammar-based compression algorithm, since it consistently offers better compression ratios than other algorithms in the literature. To accelerate compression times, we propose block-based RPFC (BRPFC) which consists in independently compressing small blocks of the dictionary. For further accelerated compression times especially on large string dictionaries, we also propose an alternative version of BRPFC that uses sampling to speed up compression. Moreover, to accelerate access times, we devise a vectorized access method, using $$\hbox {Intel}^{\circledR }$$ Intel ® Advanced Vector Extensions 512 ($$\hbox {Intel}^{\circledR }$$ Intel ® AVX-512). Our experimental evaluation shows that sampled BRPFC offers compression times up to 190 $$\times $$ × faster than RPFC, and random string lookups 2.3 $$\times $$ × faster than RPFC on average. These results move our modified RPFC into a practical range for use in database systems because the overhead of Re-Pair-based compression for access times can be reduced by 2 $$\times $$ × .

APA, Harvard, Vancouver, ISO, and other styles

35

Guo, Zhan Xi, Zhi Xin Ma, Yu Sheng Xu, and Li Liu. "An Optimized LCP Table Based Algorithm for Frequent String Mining." Applied Mechanics and Materials 20-23 (January 2010): 653–58. http://dx.doi.org/10.4028/www.scientific.net/amm.20-23.653.

Full text

Abstract:

Given m databases D1,...,Dm of strings, the purpose of the frequent string mining is to find all strings that fulfill certain constraints of all string databases. In this paper, a useful data structure is proposed to construct suffix and LCP table which can reduce the total space consumption of string mining efficiently. We demonstrate the use of this data structure by optimizing the algorithm proposed by A.Kügel et al [7] and present the improved algorithm. It is achieved that the space consumption in our algorithm is proportional to the length of the largest string of all databases. A set of comprehensive performance experiments shows that the processing rate is enhanced because amount of items are reduced in new data structure.

APA, Harvard, Vancouver, ISO, and other styles

36

TSAY, JONG-CHUANG. "DESIGNING A SYSTOLIC ALGORITHM FOR GENERATING WELL-FORMED PARENTHESIS STRINGS." Parallel Processing Letters 14, no. 01 (March 2004): 83–97. http://dx.doi.org/10.1142/s0129626404001738.

Full text

Abstract:

A parenthesis string is a string of left and right parentheses. The string is well-formed when it consists of balanced pairs of left and right parentheses. This study presents a novel systolic algorithm for generating all the well-formed parenthesis strings in lexicographical order. The algorithm is cost-optimal and is run on a linear array of processors such that each well-formed parenthesis string can be generated in three time steps. The processor array is appropriate for VLSI implementation, since it has the features of modularity, regularity, and local connection.

APA, Harvard, Vancouver, ISO, and other styles

37

Kaysar, Mohammad Shibli, and Mohammad Ibrahim Khan. "A Modified Median String Algorithm for Gene Regulatory Motif Classification." Symmetry 12, no. 8 (August 14, 2020): 1363. http://dx.doi.org/10.3390/sym12081363.

Full text

Abstract:

Consensus string is a significant feature of a deoxyribonucleic acid (DNA) sequence. The median string is one of the most popular exact algorithms to find DNA consensus. A DNA sequence is represented using the alphabet Σ= {a, c, g, t}. The algorithm generates a set of all the 4l possible motifs or l-mers from the alphabet to search a motif of length l. Out of all possible l-mers, it finds the consensus. This algorithm guarantees to return the consensus but this is NP-complete and runtime increases with the increase in l-mer size. Using transitional probability from the Markov chain, the proposed algorithm symmetrically generates four subsets of l-mers. Each of the subsets contains a few l-mers starting with a particular letter. We used these reduced sets of l-mers instead of using 4ll-mers. The experimental result shows that the proposed algorithm produces a much lower number of l-mers and takes less time to execute. In the case of l-mer of length 7, the proposed system is 48 times faster than the median string algorithm. For l-mer of size 7, the proposed algorithm produces only 2.5% l-mer in comparison with the median string algorithm. While compared with the recently proposed voting algorithm, our proposed algorithm is found to be 4.4 times faster for a longer l-mer size like 9.

APA, Harvard, Vancouver, ISO, and other styles

38

EL EMARY, IBRAHIEM M. M., and MOHAMMED S. M. JABER. "A NOVEL ALGORITHM FOR SOLVING THE STRING MATCHING PROBLEM." International Journal of Computational Intelligence and Applications 06, no. 04 (December 2006): 499–510. http://dx.doi.org/10.1142/s1469026806002040.

Full text

Abstract:

The string matching problem consists of finding one or more, generally all, exact occurrences of a pattern P in a text T. This paper presents a new algorithm for solving the string matching problem. Application of the proposed algorithm assists in improving the search process of a specific pattern in a certain unchangeable text through decreasing the number of character comparisons. Operation concept of such an algorithm depends on pattern reading to obtain the pattern length and the pattern first character and then a search is done in a table of two columns: the first column represents the word length in the text and the second one represents the start positions of each word classified by the same length. After that the algorithm just searches the words of the same length. Our experimental results depend mainly on comparing the performance of our algorithm with the well-known pattern matching algorithms such as Boyer–Moor's and Boyer–Moor–Galil's. The comparison between our algorithm and others are done in terms of the number of characters compared for different sizes of text. The output results show that our algorithm performs better than the others in terms of this parameter.

APA, Harvard, Vancouver, ISO, and other styles

39

Leonardo, Brinardi, and Seng Hansun. "Text Documents Plagiarism Detection using Rabin-Karp and Jaro-Winkler Distance Algorithms." Indonesian Journal of Electrical Engineering and Computer Science 5, no. 2 (February 1, 2017): 462. http://dx.doi.org/10.11591/ijeecs.v5.i2.pp462-471.

Full text

Abstract:

Plagiarism is an act that is considered by the university as a fraud by taking someone ideas or writings without mentioning the references and claimed as his own. Plagiarism detection system is generally implement string matching algorithm in a text document to search for common words between documents. There are some algorithms used for string matching, two of them are Rabin-Karp and Jaro-Winkler Distance algorithms. Rabin-Karp algorithm is one of compatible algorithms to solve the problem of multiple string patterns, while, Jaro-Winkler Distance algorithm has advantages in terms of time. A plagiarism detection application is developed and tested on different types of documents, i.e. doc, docx, pdf and txt. From the experimental results, we obtained that both of these algorithms can be used to perform plagiarism detection of those documents, but in terms of their effectiveness, Rabin-Karp algorithm is much more effective and faster in the process of detecting the document with the size more than 1000 KB.

APA, Harvard, Vancouver, ISO, and other styles

40

Nikonov, V. V., and A. N. Tsirulev. "Pauli basis formalism in quantum computations." Mathematical Modelling and Geometry, no. 3 (November 25, 2020): 1–14. http://dx.doi.org/10.26456/mmg/2020-831.

Full text

Abstract:

This article deals with quantum computations in the Pauli basis whose elements are usually identified with the Pauli strings. This approach allows us to represent quantum states, observables, and unitary operators in the unified form of linear combination of Pauli strings, so that all operations can be reduced to the string compositions. Nevertheless a formal justification of the Pauli basis for quantum computations should be based on the strong results of complex linear algebra and the theory of Hilbert spaces. We briefly review the main features of Pauli strings for quantum states and unitary operators, and also the key operations with them, including an algorithm for string compositions and a transformation algorithm from the standard basis to the Pauli basis.

APA, Harvard, Vancouver, ISO, and other styles

41

Pandey, Garima, Mamta Martolia, and Nitin Arora. "A Novel String Matching Algorithm and Comparison with KMP Algorithm." International Journal of Computer Applications 179, no. 3 (December 15, 2017): 6–8. http://dx.doi.org/10.5120/ijca2017915712.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Mohammad, Ababneh, Oqeili Saleh, and Rawan A. Abdeen. "Occurrences Algorithm for String Searching Based on Brute-force Algorithm." Journal of Computer Science 2, no. 1 (January 1, 2006): 82–85. http://dx.doi.org/10.3844/jcssp.2006.82.85.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Irawan, Candra, and Mudafiq Riyan Pratama. "Perbandingan Algoritma Boyer-Moore dan Brute Force pada Pencarian Kamus Besar Bahasa Indonesia Berbasis Android." BIOS : Jurnal Teknologi Informasi dan Rekayasa Komputer 1, no. 2 (February 11, 2021): 54–60. http://dx.doi.org/10.37148/bios.v1i2.13.

Full text

Abstract:

String matching is an algorithm for matching a text to another text or also known as a text search. There are several algorithms that can be used for string matching, including the Boyer-Moore algorithm and the Brute Force algorithm. The Boyer-Moore algorithm is a string matching algorithm published by Robert S. Boyer and J. Strother Moore in 1977. This algorithm is considered the most efficient algorithm in general applications. The Boyer-Moore algorithm starts matching characters from the pattern on the right. While the Brute Force algorithm is an algorithm that matches a pattern with all text between 0 and n-m to find the existence of a pattern in the text. These two algorithms have different patterns in the search process. In this article, a comparative analysis of the performance of the Boyer-Moore and Brute Force algorithms is carried out in a case study of the search for the Big Indonesian Dictionary (KBBI) based on Android. The search process is carried out by searching based on words and word descriptions. The results of this study indicate that the criteria for running time, the Brute Force algorithm is faster than the Boyer-Moore algorithm with the total running time of the Brute Force algorithm is 168.3 ms in words, 6994.16 ms in word descriptions, while the Boyer-Moore algorithm for running time reached 304.7 ms on the word, 8654.77 ms on the word description. In the testing criteria based on related keywords, the two algorithms can display the same list of related keywords.

APA, Harvard, Vancouver, ISO, and other styles

44

ATHAR, TANVER, CARL BARTON, WIDMER BLAND, JIA GAO, COSTAS S. ILIOPOULOS, CHANG LIU, and SOLON P. PISSIS. "Fast circular dictionary-matching algorithm." Mathematical Structures in Computer Science 27, no. 2 (May 11, 2015): 143–56. http://dx.doi.org/10.1017/s0960129515000134.

Full text

Abstract:

Circular string matching is a problem which naturally arises in many contexts. It consists in finding all occurrences of the rotations of a pattern of length m in a text of length n. There exist optimal worst- and average-case algorithms for circular string matching. Here, we present a suboptimal average-case algorithm for circular string matching requiring time $\mathcal{O}$(n) and space $\mathcal{O}$(m). The importance of our contribution is underlined by the fact that the proposed algorithm can be easily adapted to deal with circular dictionary matching. In particular, we show how the circular dictionary-matching problem can be solved in average-case time $\mathcal{O}$(n + M) and space $\mathcal{O}$(M), where M is the total length of the dictionary patterns, assuming that the shortest pattern is sufficiently long. Moreover, the presented average-case algorithms and other worst-case approaches were also implemented. Experimental results, using real and synthetic data, demonstrate that the implementation of the presented algorithms can accelerate the computations by more than a factor of two compared to the corresponding implementation of other approaches.

APA, Harvard, Vancouver, ISO, and other styles

45

FADHILLAH, YUNUS. "PENDETEKSIAN SOURCE CODE PLAGIARISM DENGAN ALGORITMA RABIN-KARP PADA ONLINE JUDGE." Jupiter: Journal of Computer & Information Technology 2, no. 1 (July 9, 2021): 13–32. http://dx.doi.org/10.53990/cist.v2i1.114.

Full text

Abstract:

The difficulty of testing the truth of the source code and the detection of plagiarismsource code is the underlying problem of this research. The string matchingalgorithm is the main algorithm required in the detection of source code plagiarism.Currently, there are many existing strings matching algorithms, therefore it isnecessary to compare and select the appropriate string matching algorithm to theexisting requirement. As for the system, the researcher conducts a literature study and direct observation to find the appropriate source code testing system. The Rabin-Karp algorithm is chosen based on the average of a good time and space complexity. And also can be modified, so that the Rabin-Karp algorithm can be made in such a way that can meet all the needs that exist. As for the system testing source code researchers choose the online judge system because the system in the test is objective.

APA, Harvard, Vancouver, ISO, and other styles

46

Abdul-Jabbar, Safa S., Alaa K. Farhan, Abdelaziz A. Abdelhamid, and Mohamed E. Ghoneim. "Razy: A String Matching Algorithm for Automatic Analysis of Pathological Reports." Axioms 11, no. 10 (October 12, 2022): 547. http://dx.doi.org/10.3390/axioms11100547.

Full text

Abstract:

Pathology reports are necessary for specialists to make an appropriate diagnosis of diseases in general and blood diseases in particular. Therefore, specialists check blood cells and other blood details. Thus, to diagnose a disease, specialists must analyze the factors of the patient’s blood and medical history. Generally, doctors have tended to use intelligent agents to help them with CBC analysis. However, these agents need analytical tools to extract the parameters (CBC parameters) employed in the prediction of the development of life-threatening bacteremia and offer prognostic data. Therefore, this paper proposes an enhancement to the Rabin–Karp algorithm and then mixes it with the fuzzy ratio to make this algorithm suitable for working with CBC test data. The selection of these algorithms was performed after evaluating the utility of various string matching algorithms in order to choose the best ones to establish an accurate text collection tool to be a baseline for building a general report on patient information. The proposed method includes several basic steps: Firstly, the CBC-driven parameters are extracted using an efficient method for retrieving data information from pdf files or images of the CBC tests. This will be performed by implementing 12 traditional string matching algorithms, then finding the most effective ways based on the implementation results, and, subsequently, introducing a hybrid approach to address the shortcomings or issues in those methods to discover a more effective and faster algorithm to perform the analysis of the pathological tests. The proposed algorithm (Razy) was implemented using the Rabin algorithm and the fuzzy ratio method. The results show that the proposed algorithm is fast and efficient, with an average accuracy of 99.94% when retrieving the results. Moreover, we can conclude that the string matching algorithm is a crucial tool in the report analysis process that directly affects the efficiency of the analytical system.

APA, Harvard, Vancouver, ISO, and other styles

47

GROVER, LOV K. "AN IMPROVED QUANTUM SCHEDULING ALGORITHM." International Journal of Foundations of Computer Science 14, no. 05 (October 2003): 715–21. http://dx.doi.org/10.1142/s0129054103001984.

Full text

Abstract:

The scheduling problem consists of finding a common 1 in two remotely located N bit strings. Denote the number of 1s in the string with the fewer 1s by ∊N. Classically, it needs Ω(∊N log 2 N) bits of communication to find the common 1. The best known quantum algorithms require about [Formula: see text] qubits of communication. This paper gives a quantum algorithm to find the common 1 with only [Formula: see text] qubits of communication.

APA, Harvard, Vancouver, ISO, and other styles

48

NGASSAM, ERNEST KETCHA, BRUCE W. WATSON, and DERRICK G. KOURIE. "DYNAMIC ALLOCATION OF FINITE AUTOMATA STATES FOR FAST STRING RECOGNITION." International Journal of Foundations of Computer Science 17, no. 06 (December 2006): 1307–23. http://dx.doi.org/10.1142/s0129054106004431.

Full text

Abstract:

The spatial and temporal locality of reference on which cache memory relies to minimize cache swaps, is exploited to design a new algorithm for finite automaton string recognition. It is shown that the algorithm, referred to as the Dynamic State Allocation algorithm outperforms the traditional table-driven algorithm for strings that tend to repeatedly access the same set of states, provided that the string is long enough to amortize the allocation cost. Further improvements on the algorithm result in even better performance.

APA, Harvard, Vancouver, ISO, and other styles

49

CHRISTOU, MICHALIS, MAXIME CROCHEMORE, and COSTAS S. ILIOPOULOS. "IDENTIFYING ALL ABELIAN PERIODS OF A STRING IN QUADRATIC TIME AND RELEVANT PROBLEMS." International Journal of Foundations of Computer Science 23, no. 06 (September 2012): 1371–84. http://dx.doi.org/10.1142/s0129054112500190.

Full text

Abstract:

Abelian periodicity of strings has been studied extensively over the last years. In 2006 Constantinescu and Ilie defined the abelian period of a string and several algorithms for the computation of all abelian periods of a string were given. In contrast to the classical period of a word, its abelian version is more flexible, factors of the word are considered the same under any internal permutation of their letters. We show two O(|y|2) algorithms for the computation of all abelian periods of a string y. The first one maps each letter to a suitable number such that each factor of the string can be identified by the unique sum of the numbers corresponding to its letters and hence abelian periods can be identified easily. The other one maps each letter to a prime number such that each factor of the string can be identified by the unique product of the numbers corresponding to its letters and so abelian periods can be identified easily. We also define weak abelian periods on strings and give an O(|y|log(|y|)) algorithm for their computation, together with some other algorithms for more basic problems.

APA, Harvard, Vancouver, ISO, and other styles

50

Parshukova, N. B. "CRYPTOGRAPHIC ALGORITHMS IN SPREADSHEETS." Informatics in school, no. 8 (November 9, 2019): 51–55. http://dx.doi.org/10.32517/2221-1993-2019-18-8-51-55.

Full text

Abstract:

The article examines three well known cryptographic algorithm — Skytale, Caesar's cipher, Vigenere's cipher and the method of their implementation using spreadsheets. Functions on work with strings, such as calculation of string length, search of a substring position in a string, substring selection, concatenation are considered.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!