Questions tagged [string-matching]
The string-matching tag has no summary.
39 questions
1
vote
1
answer
192
views
Data structure for grouping strings in a collection when they share common substrings [closed]
I am looking for a data structure and an algorithm to manage a dynamic collection of strings, but grouping strings that have a substring in common. I try to describe it through an example.
@Christophe:...
-1
votes
3
answers
439
views
Is there a text distance (or string similarity) algorithm which accounts for the distance between characters?
I'm interested in finding a text distance (or string similarity) algorithm which computes a greater distance (or lower similarity) when characters are further apart.
For example, I want the distance ...
- 159
2
votes
2
answers
1k
views
Are there typo-tolerance algorithms (as opposed to string similarity)? [closed]
I want to build a search with basic typo tolerance.
There are quite a few string similarity algorithms (and implementations for almost all languages I guess).
However, humans tend to make some typos ...
- 255
2
votes
0
answers
250
views
Algorithm to search very long blacklist in another very long data set
I have two data sets. The first data set has approx. 50.000 movie and song titles and the second one have 20.000 blacklist strings. I am looking for the best algorithm to detect movie/song title which ...
- 336
1
vote
1
answer
260
views
Data Matching In VBA - Best way to deal with dynamic data and user entry?
Background
I am currently building this project with VBA, just to keep in the back of your mind when thinking about my question.
Imagine 2 adjacent blocks, in Excel. The first block is made up of ...
- 27
1
vote
0
answers
224
views
Name matching in SWIFT messages
Here i am basically looking for performance improvement.
I need to match names in a SWIFT message (Let's say MT 103) against sanctions lists (sanctions lists by UN, by OFAC, some custom lists) and ...
- 229
2
votes
3
answers
2k
views
Algorithm for optimizing text compression
I am looking for text compression algorithms (natural language compression, rather than compression of arbitrary binary data).
I have seen for example An Efficient Compression Code for Text ...
- 2,757
1
vote
0
answers
218
views
phonetic algorithms for words that aren't surnames?
I've been doing a little research into algorithms for matching spelling mistakes in names. From Soundex through to metaphone and Beider-Morse. All of these algorithms generally focus on last names ...
- 323
1
vote
1
answer
188
views
Find a string in list of strings
Background:
I am writing an application for a small embedded device. There is a static list of strings: currently about 500 strings and string length is 12 characters on average. The list might ...
- 137
2
votes
4
answers
3k
views
What is the optimal way to perform 5000 unique string replace functions in terms of performance?
Restructuring some code, and the way I built it up over time has portions that look something like this:
s.replace("ABW"," Aruba ");
s.replace("AFG"," Afghanistan ");
s.replace("AGO"," Angola ");
s....
- 3,649
2
votes
1
answer
4k
views
Efficient multiple substrings search
I have many substrings(2-5 words each) which I would like to search in some text of about 40-50 words length. What is the most efficient way to flag matching substrings.
Currently I am simply using:
...
- 121
6
votes
2
answers
4k
views
Detecting plagiarism – what algorithm?
I'm currently writing a program to read a body of text and compare it to search-engine results (from searching for substrings of the given text), with the goal of detecting plagiarism in, for example, ...
- 189
-6
votes
2
answers
349
views
Which piece of code is more efficient with respect to Time and Memory cost? [closed]
Code 1:
private static int myCompare(String a, String b) {
/* my version of the compareTo method from the String Java class */
int len1 = a.length();
int len2 = b.length();
if (...
39
votes
7
answers
52k
views
What algorithm would you best use for string similarity?
I am designing a plugin to uniquely identify content on various web pages, based on addresses.
So I may have one address which looks like:
1 someawesome street, anytown, F100 211
later I may find ...
- 531
3
votes
3
answers
155
views
Replace strings based on substring match
I have N strings and M search-replace pairs. Each of the strings contains exactly one of the search pair and the whole string needs to be replaced by the replace pair.
Say you have returns,between,...
- 373
2
votes
3
answers
2k
views
Algorithm to find maximum matched units
I will try to explain my objective with an example which will be easier to understand.
Suppose I have a sentence like "A B C D E F G H".(Each word seperated using single space).
I have a Database ...
- 87
7
votes
2
answers
320
views
Finding and counting equal substrings in a set of strings
I'm thinking about a way of finding similar parts in Strings. I have a set of strings of varying length i.e:
The quick brown fox jumps
fox force five
the bunny is much quicker than the fox
is
First, i ...
- 207
0
votes
1
answer
2k
views
Most Pythonic way to remove first match of potential leading strings?
This is a bit difficult to describe, but I'll do my best.
In Python, I can use string.startswith(tuple) to test for multiple matches. But startswith only returns a boolean answer, whether or not it ...
- 115
6
votes
4
answers
6k
views
Is "use "abc".equals(myString) instead of myString.equals("abc") to avoid null pointer exception" already problematic in terms of business logic?
I heard numerous times that when comparing Strings in Java, to avoid null pointer exception, we should use "abc".equals(myString) instead of myString.equals("abc"), but my question is, is this idea ...
- 5,893
24
votes
5
answers
4k
views
Is there any good search algorithm for a single character?
I know several basic string-matching algorithms such as KMP or Boyer-Moore, but all of those analyze the pattern before searching.However, if one has a single character, there is not much to analyze.
...
- 365
-1
votes
1
answer
1k
views
Find missing number in sequence in string [closed]
I have a string that contains numbers in sequence. There are no delimiters between numbers. I have to find missing number in that sequence. For example:
176517661768 is missing the number: 1767
...
- 31
3
votes
2
answers
1k
views
Burrows-Wheeler transform backward search: how to find suffix index?
BWT backward search algorithm is pretty straightforward if we only need the multiplicity of a pattern. However I also need to find the suffix indices (i.e. positions in the reference string where a ...
- 131
4
votes
2
answers
2k
views
why regex, when using global search and {0,} quantifier, match the end of the string?
I have asked a question here about js, regex, quantifiers and global search. I've understood finally how this works, but, let's take a concrete example and then I`ll write my question.
Based on the ...
- 41
1
vote
0
answers
416
views
clustering of strings with variable-length prefixes
I've got bunch of strings with variable-length prefixes (or postfixes - I can always revert them) as follows:
0155555555
523455555555
755555555
...
87129999999999999
119999999999999
09119999999999999
...
- 232
0
votes
0
answers
623
views
scrabble solving with maximum score
I was asked a question
You are given a list of characters, a score associated with each character and a dictionary of valid words ( say normal English dictionary ). you have to form a word out ...
- 3
0
votes
2
answers
184
views
Is there a approximate string comparison function which is odd like mathematical functions are odd?
I say odd like a mathematical function, a mathematical function is odd if
f(-x) = -f(x)
I understand that comparing two strings may seem to have little to do with this, because the arguments cannot ...
- 111
0
votes
0
answers
1k
views
Compare names and the use of Levenshtein's algorithm
I need to cross names from two lists. What is the best away to compare the names? As you may expect, in one list we can have the complete name, on the other just the first and last.
Besides that, ...
- 285
1
vote
1
answer
96
views
Why try to match for nth negatives, as opposed to matching lesser positives?
My Title clearly indicated my lack of understanding about the core concept for pattern matching - specifically using .HTACCESS to block Bad-Bots from accessing a site, which they do in order to crawl ...
user172258
0
votes
1
answer
179
views
What's the algorithm should I use for seeing how well 2 strings match?
Suppose I have 2 strings:
string1 = "home/lisa/Music/some_files/01.05 - Garden Ground.mp3"
string2 = "Music/Jim Smith/Unknown/(Deluxe Version/Garden Ground).mp3"
string4 = "Music/Jim Smith/Unknown/00 ...
- 101
3
votes
2
answers
938
views
String Searching algorithm
A title for a movie can be ambiguous. (Eg. The Lord of the Rings, Lord of the Rings, Lord of the Rings, The)
There exists a database entry that has a list of movie titles mapped to a unique ...
- 39
5
votes
2
answers
2k
views
Any reasons why SQL-92 changed *, ? into %, _?
Do you know any reasons why SQL-92 standard has changed glob pattern wildcard characters from * and ? (SQL-89) to % and _?
Currently I need to do mask conversions to allow users searching data with * ...
- 672
2
votes
1
answer
1k
views
Matching algorithms in context of data quality problems
I work for an organization that has lots of databases containing person information. The data quality is poor. One case was a surname I found like this (this is the worst-case scenario):
Mark "...
- 7,139
0
votes
0
answers
264
views
Similar problem to word break
I have a list of strings say L and an array of words say A. I want to find a string from the list L that is a best match to a string created from the permutations of the words in the array.
The ...
- 111
2
votes
3
answers
6k
views
Can regexp be used to check for palindromes?
Can regexp pattern matching be used to check for palindromes within a given text in Java?
My intuition is that in order to check for palindromes, we may need to remember the character that was parsed,...
- 135
2
votes
2
answers
7k
views
Filtering common starting/ending characters from array/list of strings
Ok so for example I have an array of strings with each string as below:
364VMS1029
364VMSH920
364VMSH192
364VMSU839
364VMN2382
364VMR223
364VMR2X3
364VMN829
364VMN8757
364VMN831
How can I ...
- 103
3
votes
4
answers
3k
views
fast n-gram access data structure
TL;DR
Is there a data structure that'd quickly let me match words at any point (e.g., 'foo' matches 'foobar' and 'zoofoo'), and, ideally, returns a list of "characters that show up after the needle" ...
- 454
3
votes
0
answers
202
views
String and Suffix Matching from a Suffix List
I'm having trouble finding an algorithm that matches (or fails to match) a substring of a string to a suffix from a list of suffixes. The hits I'm finding are for suffix trees and suffix arrays, but ...
user118658
2
votes
1
answer
222
views
Comparing strings against a pool of words
I am creating an app where the user enters 8 characters. After he enters the string I have to see if it is an eight letter word. If not, check if contains a seven letter word etc.
I am checking ...
2
votes
6
answers
3k
views
Find pattern in a string [closed]
How would one approach the following question:
We have two strings: a normal alphanumeric string and a pattern string. the pattern string can be composed by alphanumeric chars plus the char "?&...
