Log in

Relevant bibliographies by topics / Approximate string matching problem / Journal articles

Journal articles on the topic 'Approximate string matching problem'

To see the other types of publications on this topic, follow the link: Approximate string matching problem.

Author: Grafiati

Published: 10 December 2022

Last updated: 28 January 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 'Approximate string matching problem.'

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

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

2

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

3

Bertossi, A. A., F. Luccio, L. Pagli, and E. Lodi. "A Parallel Solution to the Approximate String Matching Problem." Computer Journal 35, no. 5 (October 1, 1992): 524–26. http://dx.doi.org/10.1093/comjnl/35.5.524.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Yang, Zhenglu, Jianjun Yu, and Masaru Kitsuregawa. "Fast Algorithms for Top-k Approximate String Matching." Proceedings of the AAAI Conference on Artificial Intelligence 24, no. 1 (July 5, 2010): 1467–73. http://dx.doi.org/10.1609/aaai.v24i1.7527.

Full text

Abstract:

Top-k approximate querying on string collections is an important data analysis tool for many applications, and it has been exhaustively studied. However, the scale of the problem has increased dramatically because of the prevalence of the Web. In this paper, we aim to explore the efficient top-k similar string matching problem. Several efficient strategies are introduced, such as length aware and adaptive q-gram selection. We present a general q-gram based framework and propose two efficient algorithms based on the strategies introduced. Our techniques are experimentally evaluated on three real data sets and show a superior performance.

APA, Harvard, Vancouver, ISO, and other styles

5

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

6

Wang, J. F., Z. R. Li, C. Z. Cai, and Y. Z. Chen. "Assessment of approximate string matching in a biomedical text retrieval problem." Computers in Biology and Medicine 35, no. 8 (October 2005): 717–24. http://dx.doi.org/10.1016/j.compbiomed.2004.06.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Sadeh, Ilan. "Universal Data Compression Algorithm Based on Approximate String Matching." Probability in the Engineering and Informational Sciences 10, no. 4 (October 1996): 465–86. http://dx.doi.org/10.1017/s0269964800004502.

Full text

Abstract:

A practical source coding scheme based on approximate string matching is proposed. It is an approximate fixed-length string matching data compression combined with a block-coder based on the empirical distribution. A lemma on approximate string matching, which is an extension of the Kac Lemma, is proved. It is shown, based on the lemma, that the deterministic algorithm converts the stationary and ergodic source, u, into an output process v, and under the assumption that v is a stationary process, after the scheme has run for an infinite time, the optimal compression ratio R(D) is achieved. This reduces the problem of the universal lossy coder to the proof of stationarity of the output process ν in the proposed algorithm. The main advantages of the proposed method are the asymptotic sequential behavior of the encoder and the simplicity of the decoder.

APA, Harvard, Vancouver, ISO, and other styles

8

Ahmed, Pritom, A. S. M. Shohidull Islam, and M. Sohel Rahman. "A graph-theoretic model to solve the approximate string matching problem allowing for translocations." Journal of Discrete Algorithms 23 (November 2013): 143–56. http://dx.doi.org/10.1016/j.jda.2013.08.004.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

FREDRIKSSON, KIMMO, VELI MÄKINEN, and GONZALO NAVARRO. "FLEXIBLE MUSIC RETRIEVAL IN SUBLINEAR TIME." International Journal of Foundations of Computer Science 17, no. 06 (December 2006): 1345–64. http://dx.doi.org/10.1142/s0129054106004455.

Full text

Abstract:

Music sequences can be treated as texts in order to perform music retrieval tasks on them. However, the text search problems that result from this modeling are unique to music retrieval. Up to date, several approaches derived from classical string matching have been proposed to cope with the new search problems, yet each problem had its own algorithms. In this paper we show that a technique recently developed for multipattern approximate string matching is flexible enough to be successfully extended to solve many different music retrieval problems, as well as combinations thereof not addressed before. We show that the resulting algorithms are average-optimal in many cases and close to average-optimal otherwise. Empirically, they are much better than existing approaches in many practical cases.

APA, Harvard, Vancouver, ISO, and other styles

10

ŠIMŮNEK, MARTIN, and BOŘIVOJ MELICHAR. "BORDERS AND FINITE AUTOMATA." International Journal of Foundations of Computer Science 18, no. 04 (August 2007): 859–71. http://dx.doi.org/10.1142/s0129054107005029.

Full text

Abstract:

A border of a string is a prefix of the string that is simultaneously its suffix. It is one of the basic stringology keystones used as a part of many algorithms in pattern matching, molecular biology, computer-assisted music analysis and others. The paper offers the automata-theoretical description of Iliopoulos's ALL_BORDERS algorithm. The algorithm finds all borders of a string with don't care symbols. We show that ALL_BORDERS algorithm is an implementation of a finite state transducer of specific form. We describe how such a transducer can be constructed and what should be the input string like. The described transducer finds a set of lengths of all borders. Last but not least, we define approximate borders and show how to find all approximate borders of a string when we concern Hamming distance definition. Our solution of this problem is based on transducers again. This allows us to use analogy with automata-based pattern matching methods. Finally we discuss conditions under which the same principle can be used for other distance measures.

APA, Harvard, Vancouver, ISO, and other styles

11

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

12

CANTONE, DOMENICO, SALVATORE CRISTOFARO, and SIMONE FARO. "NEW EFFICIENT BIT-PARALLEL ALGORITHMS FOR THE (δ, α)-MATCHING PROBLEM WITH APPLICATIONS IN MUSIC INFORMATION RETRIEVAL." International Journal of Foundations of Computer Science 20, no. 06 (December 2009): 1087–108. http://dx.doi.org/10.1142/s0129054109007054.

Full text

Abstract:

We present new efficient variants of the (δ, α)-Sequential-Sampling algorithm, recently introduced by the authors, for the δ-approximate string matching problem with α-bounded gaps. These algorithms, which have practical applications in music information retrieval and analysis, make use of the well-known technique of bit-parallelism. An extensive comparison with the most efficient algorithms present in the literature for the same search problem shows that our newly proposed solutions achieve very good results in practice, in terms of both space and time complexity, and, in most cases, they outperform existing algorithms. Moreover, we show how to adapt our algorithms to other variants of the approximate matching problem with gaps, which are particularly relevant for their applications in other fields than music (e.g., molecular biology).

APA, Harvard, Vancouver, ISO, and other styles

13

FONTAINE, MARC, STEFAN BURKHARDT, and JUHA KÄRKKÄINEN. "BDD-BASED ANALYSIS OF GAPPED q-GRAM FILTERS." International Journal of Foundations of Computer Science 16, no. 06 (December 2005): 1121–34. http://dx.doi.org/10.1142/s0129054105003698.

Full text

Abstract:

Recently, there has been a surge of interest in gapped q-gram filters for approximate string matching. Important design parameters for filters are for example the value of q, the filter-threshold and in particular the shape (aka seed) of the filter. A good choice of parameters can improve the performance of a q-gram filter by orders of magnitude and optimizing these parameters is a nontrivial combinatorial problem. We describe a new method for analyzing gapped q-gram filters. This method is simple and generic. It applies to a variety of filters, overcomes many restrictions that are present in existing algorithms and can easily be extended to new filter variants. To implement our approach, we use an extended version of BDDs (Binary Decision Diagrams), a data structure that efficiently represents sets of bit-strings. In a second step, we define a new class of multi-shape filters and analyze these filters with the BDD-based approach. Experiments show that multi-shape filters can outperform the best single-shape filters, which are currently in use, in many aspects. The BDD-based algorithm is crucial for the design and analysis of these new and better multi-shape filters. Our results apply to the k-mismatches problem, i.e. approximate string matching with Hamming distance.

APA, Harvard, Vancouver, ISO, and other styles

14

Halappanavar, Mahantesh, John Feo, Oreste Villa, Antonino Tumeo, and Alex Pothen. "Approximate weighted matching on emerging manycore and multithreaded architectures." International Journal of High Performance Computing Applications 26, no. 4 (August 9, 2012): 413–30. http://dx.doi.org/10.1177/1094342012452893.

Full text

Abstract:

Graph matching is a prototypical combinatorial problem with many applications in high-performance scientific computing. Optimal algorithms for computing matchings are challenging to parallelize. Approximation algorithms are amenable to parallelization and are therefore important to compute matchings for large-scale problems. Approximation algorithms also generate nearly optimal solutions that are sufficient for many applications. In this paper we present multithreaded algorithms for computing half-approximate weighted matching on state-of-the-art multicore (Intel Nehalem and AMD Magny-Cours), manycore (Nvidia Tesla and Nvidia Fermi), and massively multithreaded (Cray XMT) platforms. We provide two implementations: the first uses shared work queues and is suited for all platforms; and the second implementation, based on dataflow principles, exploits special features available on the Cray XMT. Using a carefully chosen dataset that exhibits characteristics from a wide range of applications, we show scalable performance across different platforms. In particular, for one instance of the input, an R-MAT graph (RMAT-G), we show speedups of about [Formula: see text] on [Formula: see text] cores of an AMD Magny-Cours, [Formula: see text] on [Formula: see text] cores of Intel Nehalem, [Formula: see text] on Nvidia Tesla and [Formula: see text] on Nvidia Fermi relative to one core of Intel Nehalem, and [Formula: see text] on [Formula: see text] processors of Cray XMT. We demonstrate strong as well as weak scaling for graphs with up to a billion edges using up to 12,800 threads. We avoid excessive fine-tuning for each platform and retain the basic structure of the algorithm uniformly across platforms. An exception is the dataflow algorithm designed specifically for the Cray XMT. To the best of the authors' knowledge, this is the first such large-scale study of the half-approximate weighted matching problem on multithreaded platforms. Driven by the critical enabling role of combinatorial algorithms such as matching in scientific computing and the emergence of informatics applications, there is a growing demand to support irregular computations on current and future computing platforms. In this context, we evaluate the capability of emerging multithreaded platforms to tolerate latency induced by irregular memory access patterns, and to support fine-grained parallelism via light-weight synchronization mechanisms. By contrasting the architectural features of these platforms against the Cray XMT, which is specifically designed to support irregular memory-intensive applications, we delineate the impact of these choices on performance.

APA, Harvard, Vancouver, ISO, and other styles

15

Syarafina, Nadhia Nurin, and Jozua Ferjanus Palandi. "Designing a word recommendation application using the Levenshtein Distance algorithm." Matrix : Jurnal Manajemen Teknologi dan Informatika 11, no. 2 (July 15, 2021): 63–70. http://dx.doi.org/10.31940/matrix.v11i2.2419.

Full text

Abstract:

Good scriptwriting or reporting requires a high level of accuracy. The basic problem is that the level of accuracy of the authors is not the same. The low level of accuracy allows for mistyping of words in a sentence. Typing errors caused the word to become non-standard. Even worse, the word became meaningless. In this case, the recommendation application serves to provide word-writing recommendations in case of a typing error. This application can reduce the error rate of the writer when typing. One method to improve word spelling is Approximate String Matching. This method applies an approach to the string search process. The Levenshtein Distance algorithm is a part of the Approximate String-Matching method. This method, firstly, is necessary to go through the preprocessing stage to correct an incorrectly written word using the Levenshtein Distance algorithm. The application testing phase uses ten texts composed of 100 words, ten texts composed of 100 to 250 words, and ten texts composed of 250 to 500 words. The average accuracy rate of these test results was 95%, 94%, and 90%.

APA, Harvard, Vancouver, ISO, and other styles

16

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

17

Dubnov, Shlomo. "Predictive Quantization and Symbolic Dynamics." Algorithms 15, no. 12 (December 19, 2022): 484. http://dx.doi.org/10.3390/a15120484.

Full text

Abstract:

Capturing long-term statistics of signals and time series is important for modeling recurrent phenomena, especially when such recurrences are a-periodic and can be characterized by the approximate repetition of variable length motifs, such as patterns in human gestures and trends in financial time series or musical melodies. Regressive and auto-regressive models that are common in such problems, both analytically derived and neural network-based, often suffer from limited memory or tend to accumulate errors, making them sensitive during training. Moreover, such models often assume stationary signal statistics, which makes it difficult to deal with switching regimes or conditional signal dynamics. In this paper, we describe a method for time series modeling that is based on adaptive symbolization that maximizes the predictive information of the resulting sequence. Using approximate string-matching methods, the initial vectorized sequence is quantized into a discrete representation with a variable quantization threshold. Finding an optimal signal embedding is formulated in terms of a predictive bottleneck problem that takes into account the trade-off between representation and prediction accuracy. Several downstream applications based on discrete representation are described in this paper, which includes an analysis of the symbolic dynamics of recurrence statistics, motif extraction, segmentation, query matching, and the estimation of transfer entropy between parallel signals.

APA, Harvard, Vancouver, ISO, and other styles

18

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

19

Cheng, Yu-Huei, Li-Yeh Chuang, Hsueh-Wei Chang, and Cheng-Hong Yang. "Improved Candidate Drug Mining for Alzheimer’s Disease." BioMed Research International 2014 (2014): 1–8. http://dx.doi.org/10.1155/2014/897653.

Full text

Abstract:

Alzheimer's disease (AD) is the main cause of dementia for older people. Although several antidementia drugs such as donepezil, rivastigmine, galantamine, and memantine have been developed, the effectiveness of AD drug therapy is still far from satisfactory. Recently, the single nucleotide polymorphisms (SNPs) have been chosen as one of the personalized medicine markers. Many pharmacogenomics databases have been developed to provide comprehensive information by associating SNPs with drug responses, disease incidence, and genes that are critical in choosing personalized therapy. However, we found that some information from different sets of pharmacogenomics databases is not sufficient and this may limit the potential functions for pharmacogenomics. To address this problem, we used approximate string matching method and data mining approach to improve the searching of pharmacogenomics database. After computation, we can successfully identify more genes linked to AD and AD-related drugs than previous online searching. These improvements may help to improve the pharmacogenomics of AD for personalized medicine.

APA, Harvard, Vancouver, ISO, and other styles

20

Feng, Jun-Jie, Gong Zhang, and Fang-Qing Wen. "MIMO Radar Imaging Based on Smoothedl0Norm." Mathematical Problems in Engineering 2015 (2015): 1–10. http://dx.doi.org/10.1155/2015/841986.

Full text

Abstract:

For radar imaging, a target usually has only a few strong scatterers which are sparsely distributed. In this paper, we propose a compressive sensing MIMO radar imaging algorithm based on smoothedl0norm. An approximate hyperbolic tangent function is proposed as the smoothed function to measure the sparsity. A revised Newton method is used to solve the optimization problem by deriving the new revised Newton directions for the sequence of approximate hyperbolic tangent functions. In order to improve robustness of the imaging algorithm, main value weighted method is proposed. Simulation results show that the proposed algorithm is superior to Orthogonal Matching Pursuit (OMP), smoothedl0method (SL0), and Bayesian method with Laplace prior in performance of sparse signal reconstruction. Two-dimensional image quality of MIMO radar using the new method has great improvement comparing with aforementioned reconstruction algorithm.

APA, Harvard, Vancouver, ISO, and other styles

21

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

22

Baeza-Yates and G. Navarro, R. "Faster Approximate String Matching." Algorithmica 23, no. 2 (February 1999): 127–58. http://dx.doi.org/10.1007/pl00009253.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Owolabi, O., and D. R. McGregor. "Fast approximate string matching." Software: Practice and Experience 18, no. 4 (April 1988): 387–93. http://dx.doi.org/10.1002/spe.4380180407.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Shang, H., and T. H. Merrettal. "Tries for approximate string matching." IEEE Transactions on Knowledge and Data Engineering 8, no. 4 (1996): 540–47. http://dx.doi.org/10.1109/69.536247.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Ukkonen, Esko. "Algorithms for approximate string matching." Information and Control 64, no. 1-3 (January 1985): 100–118. http://dx.doi.org/10.1016/s0019-9958(85)80046-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Das, Shibsankar, and Kalpesh Kapoor. "Weighted approximate parameterized string matching." AKCE International Journal of Graphs and Combinatorics 14, no. 1 (April 1, 2017): 1–12. http://dx.doi.org/10.1016/j.akcej.2016.11.010.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Tarhio, Jorma, and Esko Ukkonen. "Approximate Boyer–Moore String Matching." SIAM Journal on Computing 22, no. 2 (April 1993): 243–60. http://dx.doi.org/10.1137/0222018.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

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

29

Russo, Luís M., Gonzalo Navarro, Arlindo Oliveira, and Pedro Morales. "Approximate String Matching with Compressed Indexes." Algorithms 2, no. 3 (September 10, 2009): 1105–36. http://dx.doi.org/10.3390/a2031105.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Holub, Jan, and Bořivoj Melichar. "Approximate string matching using factor automata." Theoretical Computer Science 249, no. 2 (October 2000): 305–11. http://dx.doi.org/10.1016/s0304-3975(00)00064-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Ukkonen, Esko, and Derick Wood. "Approximate string matching with suffix automata." Algorithmica 10, no. 5 (November 1993): 353–64. http://dx.doi.org/10.1007/bf01769703.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Baeza-Yates, Ricardo A., and Chris H. Perleberg. "Fast and practical approximate string matching." Information Processing Letters 59, no. 1 (July 1996): 21–27. http://dx.doi.org/10.1016/0020-0190(96)00083-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Tsur, Dekel. "Fast index for approximate string matching." Journal of Discrete Algorithms 8, no. 4 (December 2010): 339–45. http://dx.doi.org/10.1016/j.jda.2010.08.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Chan, Ho-Leung, Tak-Wah Lam, Wing-Kin Sung, Siu-Lung Tam, and Swee-Seong Wong. "Compressed Indexes for Approximate String Matching." Algorithmica 58, no. 2 (December 17, 2008): 263–81. http://dx.doi.org/10.1007/s00453-008-9263-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Wright, Alden H. "Approximate string matching using withinword parallelism." Software: Practice and Experience 24, no. 4 (April 1994): 337–62. http://dx.doi.org/10.1002/spe.4380240402.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Ho, ThienLuan, Seung-Rohk Oh, and HyunJin Kim. "New algorithms for fixed-length approximate string matching and approximate circular string matching under the Hamming distance." Journal of Supercomputing 74, no. 5 (November 20, 2017): 1815–34. http://dx.doi.org/10.1007/s11227-017-2192-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Liu, Jie, Xiao Yan, Xinyan Dai, Zhirong Li, James Cheng, and Ming-Chang Yang. "Understanding and Improving Proximity Graph Based Maximum Inner Product Search." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 01 (April 3, 2020): 139–46. http://dx.doi.org/10.1609/aaai.v34i01.5344.

Full text

Abstract:

The inner-product navigable small world graph (ip-NSW) represents the state-of-the-art method for approximate maximum inner product search (MIPS) and it can achieve an order of magnitude speedup over the fastest baseline. However, to date it is still unclear where its exceptional performance comes from. In this paper, we show that there is a strong norm bias in the MIPS problem, which means that the large norm items are very likely to become the result of MIPS. Then we explain the good performance of ip-NSW as matching the norm bias of the MIPS problem — large norm items have big in-degrees in the ip-NSW proximity graph and a walk on the graph spends the majority of computation on these items, thus effectively avoids unnecessary computation on small norm items. Furthermore, we propose the ip-NSW+ algorithm, which improves ip-NSW by introducing an additional angular proximity graph. Search is first conducted on the angular graph to find the angular neighbors of a query and then the MIPS neighbors of these angular neighbors are used to initialize the candidate pool for search on the inner-product proximity graph. Experiment results show that ip-NSW+ consistently and significantly outperforms ip-NSW and provides more robust performance under different data distributions.

APA, Harvard, Vancouver, ISO, and other styles

38

Barton, Carl, Costas S. Iliopoulos, and Solon P. Pissis. "Fast algorithms for approximate circular string matching." Algorithms for Molecular Biology 9, no. 1 (2014): 9. http://dx.doi.org/10.1186/1748-7188-9-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Loo, Mark,P J. ,van,der. "The stringdist Package for Approximate String Matching." R Journal 6, no. 1 (2014): 111. http://dx.doi.org/10.32614/rj-2014-011.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Cole, Richard, and Ramesh Hariharan. "Approximate String Matching: A Simpler Faster Algorithm." SIAM Journal on Computing 31, no. 6 (January 2002): 1761–82. http://dx.doi.org/10.1137/s0097539700370527.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Navarro, Gonzalo. "A guided tour to approximate string matching." ACM Computing Surveys 33, no. 1 (March 2001): 31–88. http://dx.doi.org/10.1145/375360.375365.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Lopresti, Daniel, and Andrew Tomkins. "Block edit models for approximate string matching." Theoretical Computer Science 181, no. 1 (July 1997): 159–79. http://dx.doi.org/10.1016/s0304-3975(96)00268-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Rubio, Miguel, Alfonso Alba, Martín Mendez, Edgar Arce-Santana, and Margarita Rodriguez-Kessler. "A Consensus Algorithm for Approximate String Matching." Procedia Technology 7 (2013): 322–27. http://dx.doi.org/10.1016/j.protcy.2013.04.040.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Kucherov, Gregory, Kamil Salikhov, and Dekel Tsur. "Approximate string matching using a bidirectional index." Theoretical Computer Science 638 (July 2016): 145–58. http://dx.doi.org/10.1016/j.tcs.2015.10.043.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Landau, Gad M., and Uzi Vishkin. "Fast parallel and serial approximate string matching." Journal of Algorithms 10, no. 2 (June 1989): 157–69. http://dx.doi.org/10.1016/0196-6774(89)90010-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Akutsu, Tatsuya. "Approximate string matching with don't care characters." Information Processing Letters 55, no. 5 (September 1995): 235–39. http://dx.doi.org/10.1016/0020-0190(95)00111-o.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Chang, W. I., and E. L. Lawler. "Sublinear approximate string matching and biological applications." Algorithmica 12, no. 4-5 (November 1994): 327–44. http://dx.doi.org/10.1007/bf01185431.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Navarro, Gonzalo, and Ricardo Baeza-Yates. "Very fast and simple approximate string matching." Information Processing Letters 72, no. 1-2 (October 1999): 65–70. http://dx.doi.org/10.1016/s0020-0190(99)00121-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Huynh, Trinh N. D., Wing-Kai Hon, Tak-Wah Lam, and Wing-Kin Sung. "Approximate string matching using compressed suffix arrays." Theoretical Computer Science 352, no. 1-3 (March 2006): 240–49. http://dx.doi.org/10.1016/j.tcs.2005.11.022.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Navarro, Gonzalo, and Edgar Chávez. "A metric index for approximate string matching." Theoretical Computer Science 352, no. 1-3 (March 2006): 266–79. http://dx.doi.org/10.1016/j.tcs.2005.11.037.

Full text

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!