Journal articles: 'Exact string matching problem'

1

Faro, Simone, and Thierry Lecroq. "The exact online string matching problem." ACM Computing Surveys 45, no. 2 (February 2013): 1–42. http://dx.doi.org/10.1145/2431211.2431212.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Al-Dabbagh, Sinan, and Nawaf Barnouti. "A New Efficient Hybrid String Matching Algorithm to Solve the Exact String Matching Problem." British Journal of Mathematics & Computer Science 20, no. 2 (January 10, 2017): 1–14. http://dx.doi.org/10.9734/bjmcs/2017/30497.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Al-mazroi. "A Fast Hybrid Algorithm for the Exact String Matching Problem." American Journal of Engineering and Applied Sciences 4, no. 1 (January 1, 2011): 102–7. http://dx.doi.org/10.3844/ajeassp.2011.102.107.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

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

5

Mahmood Al-Dabbagh, Sinan Sameer, Nawaf Hazim Barnouti, Mustafa Abdul Sahib Naser, and Zaid G. Ali. "Parallel Quick Search Algorithm for the Exact String Matching Problem Using OpenMP." Journal of Computer and Communications 04, no. 13 (2016): 1–11. http://dx.doi.org/10.4236/jcc.2016.413001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

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

7

Susik, Robert. "APPLYING A Q-GRAM BASED MULTIPLE STRING MATCHING ALGORITHM FOR APPROXIMATE MATCHING." Informatics Control Measurement in Economy and Environment Protection 7, no. 3 (September 30, 2017): 47–50. http://dx.doi.org/10.5604/01.3001.0010.5214.

Full text

Abstract:

We consider the application of multiple pattern matching (Multi AOSO on q-Grams) algorithm for approximate pattern matching. We propose the on-line approach which translates the problem from approximate pattern matching into a multiple pattern one (called partitioning into exact search). Presented solution allows relatively fast search multiple patterns in text with given k-differences(or mismatches). This paper presents comparison of solution based on MAG algorithm, and [4]. Experiments on DNA, English, Proteins and XML texts with up to k errors show that the new proposed algorithm achieves relatively good results in practical use.

APA, Harvard, Vancouver, ISO, and other styles

8

Liu, Na, Fei Xie, and Xindong Wu. "Suffix array for multi-pattern matching with variable length wildcards." Intelligent Data Analysis 25, no. 2 (March 4, 2021): 283–303. http://dx.doi.org/10.3233/ida-205087.

Full text

Abstract:

Approximate multi-pattern matching is an important issue that is widely and frequently utilized, when the pattern contains variable-length wildcards. In this paper, two suffix array-based algorithms have been proposed to solve this problem. Suffix array is an efficient data structure for exact string matching in existing studies, as well as for approximate pattern matching and multi-pattern matching. An algorithm called MMSA-S is for the short exact characters in a pattern by dynamic programming, while another algorithm called MMSA-L deals with the long exact characters by the edit distance method. Experimental results of Pizza & Chili corpus demonstrate that these two newly proposed algorithms, in most cases, are more time-efficient than the state-of-the-art comparison algorithms.

APA, Harvard, Vancouver, ISO, and other styles

9

Nainggolan, Efidoren L., Muhammad Syahrizal, and Saidi Ramadan Siregar. "Implementasi Algoritma Raita Pada Aplikasi Hukum Kanonik Berbasis Mobile." JURIKOM (Jurnal Riset Komputer) 7, no. 3 (June 14, 2020): 455. http://dx.doi.org/10.30865/jurikom.v7i3.2262.

Full text

Abstract:

Canonical law is an internal church law governing the Catholic Church, Eastern Orthodox Church, Eastern Orthodox Church, Anglican Communion. How the laws of the church are governed, interpreted and sometimes examined differ fundamentally between the three church bodies. in all three traditions, a canon was originally a rule accepted by an assembly, these canons formed the basis for canon law. Raita algorithm is part of the exact string matching algorithm, which is matching the string exactly with the arrangement of characters in the matched string that has the same number or sequence of characters in the string. Matching strings on the raita algorithm is done through a shift from the right of the character then to the left of the character and to the middle of the character. The problem in this research is the content of canon law in general consists of a very large number of pages of books, this makes it difficult for canonical law users to find the contents needed, then in the search it takes time to find the contents of canonical law that are searched for too many search problems. that is, too much time must be needed to find the contents of the canonical law sought

APA, Harvard, Vancouver, ISO, and other styles

10

Zheng, Qiang. "Research on an Single Pattern Matching Algorithm." Advanced Materials Research 433-440 (January 2012): 4468–74. http://dx.doi.org/10.4028/www.scientific.net/amr.433-440.4468.

Full text

Abstract:

The design of exact single pattern string matching algorithm with high performance is the basis of all string matching problems. To overcome the defects of low efficiency of pattern matching, this paper improves one of the fastest exact single pattern matching algorithms known on English text, which is SBNDM2。The simplest form of the BNDM core loop is obtained, in which there are only 5 instructions per-character read by amending the relationship between position in the pattern and bit in the bit mask. And a cross-border protection method is added to the algorithm in order to reduce the cost of cross-border inspection. Two algorithms named S2BNDM and S2BNDM′ are presented. The experimental results indicate that both S2BNDM and S2BNDM′are faster than SBNDM2 in any case.

APA, Harvard, Vancouver, ISO, and other styles

11

Son, Nguyen Van, Le Thanh Huong, and Nguyen Chi Thanh. "A two-phase plagiarism detection system based on multi-layer long short-term memory networks." IAES International Journal of Artificial Intelligence (IJ-AI) 10, no. 3 (September 1, 2021): 636. http://dx.doi.org/10.11591/ijai.v10.i3.pp636-648.

Full text

Abstract:

Finding plagiarism strings between two given documents are the main task of the plagiarism detection problem. Traditional approaches based on string matching are not very useful in cases of similar semantic plagiarism. Deep learning approaches solve this problem by measuring the semantic similarity between pairs of sentences. However, these approaches still face the following challenging points. First, it is impossible to solve cases where only part of a sentence belongs to a plagiarism passage. Second, measuring the sentential similarity without considering the context of surrounding sentences leads to decreasing in accuracy. To solve the above problems, this paper proposes a two-phase plagiarism detection system based on multi-layer long short-term memory network model and feature extraction technique: (i) a passage-phase to recognize plagiarism passages, and (ii) a word-phase to determine the exact plagiarism strings. Our experiment results on PAN 2014 corpus reached 94.26% F-measure, higher than existing research in this field.

APA, Harvard, Vancouver, ISO, and other styles

12

Razzaq, Atheer Akram Abdul, Nur’Aini Abdul Rashid, Alaa Ahmed Abbood, and Zurinahni Zainol. "The Improved Hybrid Algorithm for the Atheer and Berry-Ravindran Algorithms." International Journal of Electrical and Computer Engineering (IJECE) 8, no. 6 (December 1, 2018): 4321. http://dx.doi.org/10.11591/ijece.v8i6.pp4321-4333.

Full text

Abstract:

Exact String matching considers is one of the important ways in solving the basic problems in computer science. This research proposed a hybrid exact string matching algorithm called E-Atheer. This algorithm depended on good features; searching and shifting techniques in the Atheer and Berry-Ravindran algorithms, respectively. The proposed algorithm showed better performance in number of attempts and character comparisons compared to the original and recent and standard algorithms. E-Atheer algorithm used several types of databases, which are DNA, Protein, XML, Pitch, English, and Source. The best performancein the number of attempts is when the algorithm is executed using the pitch dataset. The worst performance is when it is used with DNA dataset. The best and worst databases in the number of character comparisons with the E-Atheer algorithm are the Source and DNA databases, respectively.

APA, Harvard, Vancouver, ISO, and other styles

13

Almazroi. "A Fast Hybrid Algorithm Approach for the Exact String Matching Problem Via Berry Ravindran and Alpha Skip Search Algorithms." Journal of Computer Science 7, no. 5 (May 1, 2011): 644–50. http://dx.doi.org/10.3844/jcssp.2011.644.650.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

de Jager, Coenrad, and Marinda Nel. "Business Process Automation: A Workflow Incorporating Optical Character Recognition and Approximate String and Pattern Matching for Solving Practical Industry Problems." Applied System Innovation 2, no. 4 (October 24, 2019): 33. http://dx.doi.org/10.3390/asi2040033.

Full text

Abstract:

Companies are relying more on artificial intelligence and machine learning in order to enhance and automate existing business processes. While the power of OCR (Optical Character Recognition) technologies can be harnessed for the digitization of image data, the digitalized text still needs to be validated and enhanced to ensure that data quality standards are met for the data to be usable. This research paper focuses on finding and creating an automated workflow that can follow image digitization and produce a dictionary consisting of the desired information. The workflow introduced consists of a three-step process that is implemented after the OCR output has been generated. With the introduction of each step, the accuracy of key-value matches of field names and values is increased. The first step takes the raw OCR output and identifies field names using exact string matching and field-values using regular expressions from an externally maintained file. The second step introduces index pairing that matches field-values to field names based on the location of the field name and value on the document. Finally, approximate string matching is introduced to the workflow, which increases accuracy. By implementing these steps, the F-measure for key-value pair matches is measured at 60.18% in the first step, 80.61% once index pairing is introduced, and finally 90.06% after approximate string matching is introduced. The research proved that accurate usable data can be obtained automatically from images with the implementation of a workflow after OCR.

APA, Harvard, Vancouver, ISO, and other styles

15

Saad, Rachid. "Finding a Longest Alternating Cycle in a 2-edge-coloured Complete Graph is in RP." Combinatorics, Probability and Computing 5, no. 3 (September 1996): 297–306. http://dx.doi.org/10.1017/s0963548300002054.

Full text

Abstract:

Jackson [10] gave a polynomial sufficient condition for a bipartite tournament to contain a cycle of a given length. The question arises as to whether deciding on the maximum length of a cycle in a bipartite tournament is polynomial. The problem was considered by Manoussakis [12] in the slightly more general setting of 2-edge coloured complete graphs: is it polynomial to find a longest alternating cycle in such coloured graphs? In this paper, strong evidence is given that such an algorithm exists. In fact, using a reduction to the well known exact matching problem, we prove that the problem is random polynomial.

APA, Harvard, Vancouver, ISO, and other styles

16

Zhang, Yufeng, Jinghao Zhang, Zeyu Cui, Shu Wu, and Liang Wang. "A Graph-based Relevance Matching Model for Ad-hoc Retrieval." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 5 (May 18, 2021): 4688–96. http://dx.doi.org/10.1609/aaai.v35i5.16599.

Full text

Abstract:

To retrieve more relevant, appropriate and useful documents given a query, finding clues about that query through the text is crucial. Recent deep learning models regard the task as a term-level matching problem, which seeks exact or similar query patterns in the document. However, we argue that they are inherently based on local interactions and do not generalise to ubiquitous, non-consecutive contextual relationships. In this work, we propose a novel relevance matching model based on graph neural networks to leverage the document-level word relationships for ad-hoc retrieval. In addition to the local interactions, we explicitly incorporate all contexts of a term through the graph-of-word text format. Matching patterns can be revealed accordingly to provide a more accurate relevance score. Our approach significantly outperforms strong baselines on two ad-hoc benchmarks. We also experimentally compare our model with BERT and show our advantages on long documents.

APA, Harvard, Vancouver, ISO, and other styles

17

Lucibello, C., and F. Ricci-Tersenghi. "The Statistical Mechanics of Random Set Packing and a Generalization of the Karp-Sipser Algorithm." International Journal of Statistical Mechanics 2014 (March 10, 2014): 1–13. http://dx.doi.org/10.1155/2014/136829.

Full text

Abstract:

We analyse the asymptotic behaviour of random instances of the maximum set packing (MSP) optimization problem, also known as maximum matching or maximum strong independent set on hypergraphs. We give an analytic prediction of the MSPs size using the 1RSB cavity method from statistical mechanics of disordered systems. We also propose a heuristic algorithm, a generalization of the celebrated Karp-Sipser one, which allows us to rigorously prove that the replica symmetric cavity method prediction is exact for certain problem ensembles and breaks down when a core survives the leaf removal process. The e-phenomena threshold discovered by Karp and Sipser, marking the onset of core emergence and of replica symmetry breaking, is elegantly generalized to Cs=e/(d-1) for one of the ensembles considered, where d is the size of the sets.

APA, Harvard, Vancouver, ISO, and other styles

18

Sheu, C. Y., F. Kurz, and P. Angelo. "AUTOMATIC 3D LANE MARKING RECONSTRUCTION USING MULTI-VIEW AERIAL IMAGERY." ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences IV-1 (September 26, 2018): 147–54. http://dx.doi.org/10.5194/isprs-annals-iv-1-147-2018.

Full text

Abstract:

<p><strong>Abstract.</strong> The 3D information of road infrastructures are gaining importance with the development of autonomous driving. The exact absolute position and height of lane markings, for example, support lane-accurate localization. Several approaches have been proposed for the 3D reconstruction of line features from multi-view airborne optical imagery. However, standard appearance-based matching approaches for 3D reconstruction are hardly applicable on lane markings due to the similar color profile of all lane markings and the lack of textures in their neighboring areas. We present a workflow for 3D lane markings reconstruction without explicit feature matching process using multi-view aerial imagery. The aim is to optimize the best 3D line location by minimizing the distance from its back projection to the detected 2D line in all the covering images. Firstly, the lane markings are automatically extracted from aerial images using standard line detection algorithms. By projecting these extracted lines onto the Semi-Global Matching (SGM) generated Digital Surface Model (DSM), the approximate 3D line segments are generated. Starting from these approximations, the 3D lines are iteratively refined based on the detected 2D lines in the original images and the viewing geometry. The proposed approach relies on precise detection of 2D lines in image space, a pre-knowledge of the approximate 3D line segments, and it heavily relies on image orientations. Nevertheless, it avoids the problem of non-textured neighborhood and is not limited to lines of finite length. The theoretical precision of 3D reconstruction with the proposed framework is evaluated.</p>

APA, Harvard, Vancouver, ISO, and other styles

19

Qian, Chao, Yang Yu, and Zhi-Hua Zhou. "Analyzing Evolutionary Optimization in Noisy Environments." Evolutionary Computation 26, no. 1 (March 2018): 1–41. http://dx.doi.org/10.1162/evco_a_00170.

Full text

Abstract:

Many optimization tasks must be handled in noisy environments, where the exact evaluation of a solution cannot be obtained, only a noisy one. For optimization of noisy tasks, evolutionary algorithms (EAs), a type of stochastic metaheuristic search algorithm, have been widely and successfully applied. Previous work mainly focuses on the empirical study and design of EAs for optimization under noisy conditions, while the theoretical understandings are largely insufficient. In this study, we first investigate how noisy fitness can affect the running time of EAs. Two kinds of noise-helpful problems are identified, on which the EAs will run faster with the presence of noise, and thus the noise should not be handled. Second, on a representative noise-harmful problem in which the noise has a strong negative effect, we examine two commonly employed mechanisms dealing with noise in EAs: reevaluation and threshold selection. The analysis discloses that using these two strategies simultaneously is effective for the one-bit noise but ineffective for the asymmetric one-bit noise. Smooth threshold selection is then proposed, which can be proved to be an effective strategy to further improve the noise tolerance ability in the problem. We then complement the theoretical analysis by experiments on both synthetic problems as well as two combinatorial problems, the minimum spanning tree and the maximum matching. The experimental results agree with the theoretical findings and also show that the proposed smooth threshold selection can deal with the noise better.

APA, Harvard, Vancouver, ISO, and other styles

20

Haj Rachid, Maan. "Two Efficient Techniques to Find Approximate Overlaps between Sequences." BioMed Research International 2017 (2017): 1–8. http://dx.doi.org/10.1155/2017/2731385.

Full text

Abstract:

The next-generation sequencing (NGS) technology outputs a huge number of sequences (reads) that require further processing. After applying prefiltering techniques in order to eliminate redundancy and to correct erroneous reads, an overlap-based assembler typically finds the longest exact suffix-prefix match between each ordered pair of the input reads. However, another trend has been evolving for the purpose of solving an approximate version of the overlap problem. The main benefit of this direction is the ability to skip time-consuming error-detecting techniques which are applied in the prefiltering stage. In this work, we present and compare two techniques to solve the approximate overlap problem. The first adapts a compact prefix tree to efficiently solve the approximate all-pairs suffix-prefix problem, while the other utilizes a well-known principle, namely, the pigeonhole principle, to identify a potential overlap match in order to ultimately solve the same problem. Our results show that our solution using the pigeonhole principle has better space and time consumption over an FM-based solution, while our solution based on prefix tree has the best space consumption between all three solutions. The number of mismatches (hamming distance) is used to define the approximate matching between strings in our work.

APA, Harvard, Vancouver, ISO, and other styles

21

Mertzios, George B., Hendrik Molter, and Viktor Zamaraev. "Sliding Window Temporal Graph Coloring." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 7667–74. http://dx.doi.org/10.1609/aaai.v33i01.33017667.

Full text

Abstract:

Graph coloring is one of the most famous computational problems with applications in a wide range of areas such as planning and scheduling, resource allocation, and pattern matching. So far coloring problems are mostly studied on static graphs, which often stand in stark contrast to practice where data is inherently dynamic and subject to discrete changes over time. A temporal graph is a graph whose edges are assigned a set of integer time labels, indicating at which discrete time steps the edge is active. In this paper we present a natural temporal extension of the classical graph coloring problem. Given a temporal graph and a natural number ∆, we ask for a coloring sequence for each vertex such that (i) in every sliding time window of ∆ consecutive time steps, in which an edge is active, this edge is properly colored (i.e. its endpoints are assigned two different colors) at least once during that time window, and (ii) the total number of different colors is minimized. This sliding window temporal coloring problem abstractly captures many realistic graph coloring scenarios in which the underlying network changes over time, such as dynamically assigning communication channels to moving agents. We present a thorough investigation of the computational complexity of this temporal coloring problem. More specifically, we prove strong computational hardness results, complemented by efficient exact and approximation algorithms. Some of our algorithms are linear-time fixed-parameter tractable with respect to appropriate parameters, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH).

APA, Harvard, Vancouver, ISO, and other styles

22

Lecroq, Thierry. "Fast exact string matching algorithms." Information Processing Letters 102, no. 6 (June 2007): 229–35. http://dx.doi.org/10.1016/j.ipl.2007.01.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Ďurian, Branislav, Jan Holub, Hannu Peltola, and Jorma Tarhio. "Improving practical exact string matching." Information Processing Letters 110, no. 4 (January 2010): 148–52. http://dx.doi.org/10.1016/j.ipl.2009.11.010.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Gunawan, Gunawan, and Aji Sudarsono. "Penerapan Exact String Matching Pencarian Data Pada Sistem Informasi Akademik Berbasis Web." J-SISKO TECH (Jurnal Teknologi Sistem Informasi dan Sistem Komputer TGD) 5, no. 2 (July 22, 2022): 214. http://dx.doi.org/10.53513/jsk.v5i2.5793.

Full text

Abstract:

Abstrak Proses pengecekan kesalahan pengetikan dengan cara manual akan menghabiskan banyak waktu. Oleh karena itu diperlukan suatu sistem yang mampu mengidentifikasi kesalahan pengetikan agar sesuai dengan kaidah penulisan EYD yang benar aplikasi ini dapat menerapkan metode string matching, dimana aplikasi pencarian pada SMAN 8 Kota Bengkulu telah menerapkan sistem manual yaitu pencatatan pada komputer kemudian diprint. Tujuan penelitian ini adalah membuat aplikasi pencarian data pada Sistem Informasi Akademik SMAN 8 Kota Bengkulu menggunakan metode exact string matching. Penerapan algoritma ini menggunakan metode RAD dan rancangan sistem dengan UML sehingga algoritma ini telah berhasil di terapkan pada Sistem Infomasi Akademik SMAN 8 Kota Bengkulu, algoritma Exact String Matching mudah diterapkan pada aplikasi pencarian data dalam bentuk String sehingga proses pemcarian data akan lebih cepat, lebih baik dan efisien sedangkan jika pencarian data dalam bentuk mendekati String maka perlu algoritma lain yang lebih kuat.Kata Kunci : Pencarian, Algoritma, Exact String MatchingAbstractThe process of checking for typing errors manually will take a lot of time. Therefore we need a system that is able to identify typing errors to match the correct EYD writing rules. This application can apply the string matching method, where the search application at SMAN 8 Bengkulu City has implemented a manual system, namely recording on a computer and then printing it. The purpose of this study is to create a data search application on the Academic Information System of SMAN 8 Bengkulu City using the exact string matching method. The application of this algorithm uses the RAD method and system design with UML so that this algorithm has been successfully applied to the Academic Information System of SMAN 8 Bengkulu City, the Exact String Matching algorithm is easy to apply to data search applications in String form so that the data search process will be faster, better and efficient, whereas if the search for data is in the form of a string close to it, it needs another algorithm that is more powerful.Keywords: Search, Algorithm, Exact String Matching

APA, Harvard, Vancouver, ISO, and other styles

25

HE, Long-Tao. "A Time Optimal Exact String Matching Algorithm." Journal of Software 16, no. 5 (2005): 676. http://dx.doi.org/10.1360/jos160676.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Hyyrö, Heikki, Martti Juhola, and Mauno Vihinen. "On exact string matching of unique oligonucleotides." Computers in Biology and Medicine 35, no. 2 (February 2005): 173–81. http://dx.doi.org/10.1016/j.compbiomed.2003.11.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Tarhio, Jorma, Jan Holub, and Emanuele Giaquinta. "Technology beats algorithms (in exact string matching)." Software: Practice and Experience 47, no. 12 (August 1, 2017): 1877–85. http://dx.doi.org/10.1002/spe.2511.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Jadhav, Ninad Jagadish. "Beowulf Cluster- PXSMAlg Parallel Exact String-Matching Algorithm." IJARCCE 7, no. 11 (November 30, 2018): 221–25. http://dx.doi.org/10.17148/ijarcce.2018.71147.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Chen, K. H., G. S. Huang, and R. C. T. Lee. "Bit-Parallel Algorithms for Exact Circular String Matching." Computer Journal 57, no. 5 (March 3, 2013): 731–43. http://dx.doi.org/10.1093/comjnl/bxt023.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Borman, Rohmat Indra. "Penerapan String Matching Dengan Algoritma Boyer Moore Pada Aplikasi Font Italic Untuk Deteksi Kata Asing." Jurnal Teknoinfo 10, no. 2 (July 15, 2016): 39. http://dx.doi.org/10.33365/jti.v10i2.9.

Full text

Abstract:

Dalam karya ilmiah penulisan untuk kata asing, seperti kata berbahasa inggris, berbahasa yunani dan bahasa lainya dibuat dengan memiringkan kata tersebut. Aplikasi pengolah kata yang biasanya digunakan adalah Microsoft Office Word. Untuk memiringkan kata asing pada Microsoft Office Word menggunakan salah satu tools yang ada di toolbar Microsoft Office Word yaitu italic. Algoritma boyer moore merupakan salah satu algoritma yang digunakan untuk melakukan pencocokan string (string matching). Algoritma ini merupakan jenis exact string matching algorithm yang melakukan pencocokan string secara tepat dengan susunan karakter dalam string yang dicocokkan memiliki jumlah maupun urutan karakter dalam string yang sama. Cara kerja algoritma ini adalah dengan melakukan pencocokan dari kanan ke kiri yaitu men-scan karakter pattern dari kanan ke kiri dimulai dari karakter paling kanan. Penerapan algoritma boyer moore pada aplikasi font italic, akan mencari semua kemungkinan kata asing di dalam dokumen microsoft office word dengan yang ada di database aplikasi untuk membuat otomatis tercetak miring.Kata kunci: Aplikasi, font italic, katas asing, algoritma, string matching, boyer moore, exact string matching.

APA, Harvard, Vancouver, ISO, and other styles

31

Klein, S. T., and D. Shapira. "The String-to-Dictionary Matching Problem." Computer Journal 55, no. 11 (February 17, 2012): 1347–56. http://dx.doi.org/10.1093/comjnl/bxs004.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Abdulrazzaq, Atheer Akram, Nur’Aini Abdul Rashid, Awsan Hassan Abdullah, Muhannad A. Abu-Hashem, and Zurinahni Zainol. "New Searching Technique of Hybrid Exact String Matching Algorithm." International Review on Computers and Software (IRECOS) 11, no. 10 (October 31, 2016): 884. http://dx.doi.org/10.15866/irecos.v11i10.10321.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Navarro, Gonzalo, and Kimmo Fredriksson. "Average complexity of exact and approximate multiple string matching." Theoretical Computer Science 321, no. 2-3 (August 2004): 283–90. http://dx.doi.org/10.1016/j.tcs.2004.03.058.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Galil, Zvi, and Raffaele Giancarlo. "On the Exact Complexity of String Matching: Lower Bounds." SIAM Journal on Computing 20, no. 6 (December 1991): 1008–20. http://dx.doi.org/10.1137/0220063.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Galil, Zvi, and Raffaele Giancarlo. "On the Exact Complexity of String Matching: Upper Bounds." SIAM Journal on Computing 21, no. 3 (June 1992): 407–37. http://dx.doi.org/10.1137/0221028.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Liu, Bing, Dan Han, and Shuang Zhang. "Approximate Chinese String Matching Techniques Based on Pinyin Input Method." Applied Mechanics and Materials 513-517 (February 2014): 1017–20. http://dx.doi.org/10.4028/www.scientific.net/amm.513-517.1017.

Full text

Abstract:

String matching is one of the most typical problems in computer science. Previous studies mainly focused on accurate string matching problem. However, with the rapid development of the computer and Internet as well as the continuously rising of new issues, people find that it has very important theoretical value and practical meaning to research and design efficient approximate string matching algorithms. Approximate string matching is also called string matching that allows errors, which mainly aims to find the pattern string in the text and database and allows k differences between the pattern string and its occurring forms in the text. For the problem of approximate string matching, though a number of algorithms have been proposed, there are fewer studies which focus on large size of alphabet . Most of experts are interested in small or middle size of alphabet . For large size of , especially for Chinese characters and Asian phonetics, there are fewer efficient algorithms. For the above reasons, this paper focuses on the approximate Chinese strings matching problem based on the pinyin input method.

APA, Harvard, Vancouver, ISO, and other styles

37

XU, Xiu-lin. "Single pattern string exact matching algorithms based on hybrid strategy." Journal of Computer Applications 28, no. 1 (June 30, 2008): 232–35. http://dx.doi.org/10.3724/sp.j.1087.2008.00232.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Cole, Richard, Ramesh Hariharan, Mike Paterson, and Uri Zwick. "Tighter Lower Bounds on the Exact Complexity of String Matching." SIAM Journal on Computing 24, no. 1 (February 1995): 30–45. http://dx.doi.org/10.1137/s0097539793245829.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Cole, Richard, and Ramesh Hariharan. "Tighter Upper Bounds on the Exact Complexity of String Matching." SIAM Journal on Computing 26, no. 3 (June 1997): 803–56. http://dx.doi.org/10.1137/s009753979324694x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Hakak, Saqib Iqbal, Amirrudin Kamsin, Palaiahnakote Shivakumara, Gulshan Amin Gilkar, Wazir Zada Khan, and Muhammad Imran. "Exact String Matching Algorithms: Survey, Issues, and Future Research Directions." IEEE Access 7 (2019): 69614–37. http://dx.doi.org/10.1109/access.2019.2914071.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Cormode, Graham, and S. Muthukrishnan. "The string edit distance matching problem with moves." ACM Transactions on Algorithms 3, no. 1 (February 2007): 1–19. http://dx.doi.org/10.1145/1186810.1186812.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Nettleton, David F., and Julian Salas. "Approximate Matching of Neighborhood Subgraphs — An Ordered String Graph Levenshtein Method." International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 24, no. 03 (June 2016): 411–31. http://dx.doi.org/10.1142/s0218488516500215.

Full text

Abstract:

Given that exact pair-wise graph matching has a high computational cost, different representational schemes and matching methods have been devised in order to make matching more efficient. Such methods include representing the graphs as tree structures, transforming the structures into strings and then calculating the edit distance between those strings. However many coding schemes are complex and are computationally expensive. In this paper, we present a novel coding scheme for unlabeled graphs and perform some empirical experiments to evaluate its precision and cost for the matching of neighborhood subgraphs in online social networks. We call our method OSG-L (Ordered String Graph-Levenshtein). Some key advantages of the pre-processing phase are its simplicity, compactness and lower execution time. Furthermore, our method is able to match both non-isomorphisms (near matches) and isomorphisms (exact matches), also taking into account the degrees of the neighbors, which is adequate for social network graphs.

APA, Harvard, Vancouver, ISO, and other styles

43

BERGERON, ANNE, and SYLVIE HAMEL. "VECTOR ALGORITHMS FOR APPROXIMATE STRING MATCHING." International Journal of Foundations of Computer Science 13, no. 01 (February 2002): 53–65. http://dx.doi.org/10.1142/s0129054102000947.

Full text

Abstract:

Vector algorithms allow the computation of an output vector r = r1 r2 ⋯ rm given an input vector e = e1 e2 ⋯ em in a bounded number of operations, independent of m the length of the vectors. The allowable operations are usually restricted to bit-wise operations available in processors, including shifts and binary addition with carry. These restrictions imple that the existence of a vector algorithm for a particular problem opens the way to extremely fast implementations, using the inherent parallelism of bit-wise operations. This paper presents general results on the existence and construction of vertor algorithms, with a particular focus on problems arising from computational biology. We show that efficient vector algorithms exist for the problem of approximate string matching with arbitrary weighted distances, generalizing a previous result by G. Myers. We also characterize a class of automata for which vector algorithms can be automatically derived from the transition table of the automata.

APA, Harvard, Vancouver, ISO, and other styles

44

Kelsey, Tom, and Lars Kotthoff. "Exact Closest String as a Constraint Satisfaction Problem." Procedia Computer Science 4 (2011): 1062–71. http://dx.doi.org/10.1016/j.procs.2011.04.113.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Rae, Gordon. "Exact Probabilities for the General Matching Problem." Educational and Psychological Measurement 56, no. 5 (October 1996): 839–42. http://dx.doi.org/10.1177/0013164496056005011.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Dutta Roy, S. C. "Exact solution of a bandpass matching problem." Circuits, Systems, and Signal Processing 19, no. 1 (January 2000): 59–69. http://dx.doi.org/10.1007/bf01229992.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Vardulakis, A. I. G., and N. Karcanias. "On the stable exact model matching problem." Systems & Control Letters 5, no. 4 (February 1985): 237–42. http://dx.doi.org/10.1016/0167-6911(85)90015-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Pandey, R. K., and S. Taruna. "Prevalent Exact String-Matching Algorithms in Natural Language Processing: A Review." Journal of Physics: Conference Series 1854, no. 1 (April 1, 2021): 012042. http://dx.doi.org/10.1088/1742-6596/1854/1/012042.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

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

50

Karcioglu, Abdullah Ammar, and Hasan Bulut. "The WM-q multiple exact string matching algorithm for DNA sequences." Computers in Biology and Medicine 136 (September 2021): 104656. http://dx.doi.org/10.1016/j.compbiomed.2021.104656.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Exact string matching problem'

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