20
votes
Accepted
What algorithm would you best use for string similarity?
Levenstein's algorithm is based on the number of insertions, deletions, and substitutions in strings.
Unfortunately it doesn't take into account a common misspelling which is the transposition of 2 ...
- 80.6k
6
votes
What is the optimal way to perform 5000 unique string replace functions in terms of performance?
The regular expression libraries in some languages let you specify a function to determine the replacement instead of a single string. That, combined with a hash of your strings and their ...
- 20.4k
5
votes
Efficient multiple substrings search
Create a regular expression from your list (something like "word1|word2|word3") and use the regular expression functions available for your language. It will hopefully create a data structure ...
5
votes
What algorithm would you best use for string similarity?
You ask about string similarity algorithms but your strings are addresses. I would submit the addresses to a location API such as Google Place Search and use the formatted_address as a point of ...
- 3,123
4
votes
Accepted
Find a string in list of strings
Your binary search is probably good enough. Alternative approaches will lead to a lot more complexity, for likely little gain.
There are a couple of optimization approaches that you can try:
A trie ...
- 135k
4
votes
What is the optimal way to perform 5000 unique string replace functions in terms of performance?
This seems like something which can be efficiently addressed by building a Trie out of all the strings that need to be replaced.
Then in one pass, go through the string to be replaced on, character ...
- 193
3
votes
Which piece of code is more efficient with respect to Time and Memory cost?
First: The two methods does two different things. stringCompare returns the alphabetic ordering of two strings which means it can be used to sort a set of strings alphabetically.
myCompare just ...
- 61k
3
votes
Are there typo-tolerance algorithms (as opposed to string similarity)?
I don't think there is a single algorithm that's going to do what you want.
For point 1 (transpositions) you can use Damerau-Levenshtein Distance, or the simpler Optimal String Alignment distance (...
- 678
2
votes
What algorithm would you best use for string similarity?
Levenshtein distance is better for words
If words are (mainly) spelled correctly then look at bag of words.
I may seem like over kill but TF-IDF and cosine similarity.
Or you could use free ...
- 1,927
2
votes
Detecting plagiarism – what algorithm?
Your intend is to compare text body with search engine results to detect plagiarism.
Unfortunately the algorithms that you consider work at character level. They are time consuming with longer texts, ...
- 80.6k
2
votes
Accepted
Detecting plagiarism – what algorithm?
This is somewhat of an XY answer but given you started with
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 ...
- 3,241
2
votes
Algorithm for optimizing text compression
Text compression algorithms
Word based compression
You already explained yourself the basic principles of a dictionary compression that works by word. However interesting article that you referred ...
- 80.6k
2
votes
What is the optimal way to perform 5000 unique string replace functions in terms of performance?
Your idea of using regexes and a hash table is probably ideal. It is likely much better to perform all replacements in a single pass instead of using multiple replacement passes, because:
correctness:...
- 135k
1
vote
Is there a text distance (or string similarity) algorithm which accounts for the distance between characters?
As others have said, you must first define "distance". Once you have done so, however, standard approaches can be used. I have implemented Levenshtein this way--most changes were counted ...
- 3,411
1
vote
Is there a text distance (or string similarity) algorithm which accounts for the distance between characters?
First: Define what the distance between two characters is. For example, p and b, g and k, d and t Are similar. A and e are reasonably similar. If I had software converting speech to text, and the ...
- 47.5k
1
vote
Are there typo-tolerance algorithms (as opposed to string similarity)?
There are a couple of string similarity algorithms that could be useful in an editor for detecting typos. The trick is to use the current position, find the start of the current token by moving back ...
- 80.6k
1
vote
What is the optimal way to perform 5000 unique string replace functions in terms of performance?
Interesting problem!
I am sure that someone can and will come up with a better solution, but here are my initial thoughts:
Your biggest bottleneck will be the continual reallocation of memory.
...
- 98
1
vote
Which piece of code is more efficient with respect to Time and Memory cost?
Method 1 is quite efficient as far as execution time and memory usage are concerned. Unfortunately, it is completely useless, so efficiency doesn't help.
Method 2 is unnecessary inefficient for most ...
- 47.5k
1
vote
What algorithm would you best use for string similarity?
Firstly, you'd have to parse the webpage for addresses, RegEx is one wrote to take however it can be very difficult to parse addresses using RegEx. You'd likely end up having to go through a list of ...
- 1,302
1
vote
Finding and counting equal substrings in a set of strings
As counting identical strings is trivial, I'll address the portion of your question about making "quicker" count as "quick". As mentioned in the comments this is called stemming. Note that stemming is ...
- 1,861
1
vote
Why try to match for nth negatives, as opposed to matching lesser positives?
This is a matter of what you want the default to be.
If you want to allow by default, you need to list the blocked ones (blacklist). If you want to deny by default, you need to list the allowed ones (...
- 18.4k
Only top scored, non community-wiki answers of a minimum length are eligible