9

I have lots of strings containing text in lots of different spellings. I am tokenizing these strings by searching for keywords and if a keyword is found I use an assoicated text for that keyword.

Let's say the search string can contain the text "schw.", "schwa." and "schwarz". I have three keywords that all resolve to the text "schwarz".

Now I'm searching for an effective way to find all the keywords without doing a string.Contains(keyword) for every single keyword.

Sample data:

H-Fuss ahorn 15 cm/SH48cm
Metall-Fuss chrom 9 cm/SH42cm
Metall-Kufe alufbg.12 cm/SH45c
Metall-Kufe verchr.12 cm/SH45c
Metall-Zylind.aluf.12cm/SH45cm
Kufe alufarbig
Metall-Zylinder hoch alufarbig
Kunststoffgl.schw. - hoch
Kunststoffgl.schw. - Standard
Kunststoffgleiter - schwarz für Sitzhoehe 42 cm

Sample keywords (key, value):

h-fuss, Holz
ahorn, Ahorn
metall, Metall
chrom, Chrom
verchr, Chrom
alum, Aluminium
aluf, Aluminium
kufe, Kufe
zylind, Zylinder
hoch, Hoch
kunststoffgl, Gleiter
gleiter, Gleiter
schwarz, Schwarz
schw., Schwarz

Sample result:

Holz, Ahorn
Metall, Chrom
Metall, Kufe, Aluminium
Metall, Kufe, Chrom
Metall, Zylinder, Aluminium
Kufe, Aluminium
Metall, Zylinder, Hoch, Aluminium
Gleiter, Schwarz, Hoch
Gleiter, Schwarz
Gleiter, Schwarz
Improve this question

5 Answers 5

Reset to default
17

This seems to fit "Algorithms using finite set of patterns"

The Aho–Corasick string matching algorithm is a string searching algorithm invented by Alfred V. Aho and Margaret J. Corasick. It is a kind of dictionary-matching algorithm that locates elements of a finite set of strings (the "dictionary") within an input text. It matches all patterns "at once", so the complexity of the algorithm is linear in the length of the patterns plus the length of the searched text plus the number of output matches. Note that because all matches are found, there can be a quadratic number of matches if every substring matches (e.g. dictionary = a, aa, aaa, aaaa and input string is aaaa).

The Rabin–Karp algorithm is a string searching algorithm created by Michael O. Rabin and Richard M. Karp in 1987 that uses hashing to find any one of a set of pattern strings in a text. For text of length n and p patterns of combined length m, its average and best case running time is O(n+m) in space O(p), but its worst-case time is O(nm). In contrast, the Aho–Corasick string matching algorithm has asymptotic worst-time complexity O(n+m) in space O(m).

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

The Aho-Crasick algorithm looks really promising. I'm currently looking at a CodeProject project implementing the algorithm: codeproject.com/KB/recipes/ahocorasick.aspx
Aho-Corasick is exactly what you want. Another solution I'd suggest is just use a regex library which also constructs a DFA, such as something based on re2 code.google.com/p/re2
recently I've ported from java very efficient implementation of Aho-Corasick: github.com/nreco/AhoCorasickDoubleArrayTrie it is really damn fast and suitable for production use.
3

I would use precompiled regular expressions for each group of keywords to match. In the background these are "compiled" to finite automata, so they are pretty fast in recognizing the pattern in your string and much faster than a Contains for each of the possible strings.

using: System.Text.RegularExpressions.

In your example:

  • "schw.", "schwa." and "schwarz"
  • new Regex(@"schw(a?\.|arz)", RegexOptions.Compiled)

Further documentation available here: http://msdn.microsoft.com/en-us/library/system.text.regularexpressions.regexoptions(v=VS.90).aspx

Improve this answer

1 Comment

That's one regex match per keyword (or group) which isn't too great. Or one truely horrendous regexp with alternation on every group. Aho-Crasick basically does the same as comiling hte horrrendours regexp into a DFA, but without the full complexity of regexps it's easier to implement.
1

If you have a fixed set of keywords you can use (f)lex, re2c or ragel

Improve this answer

1 Comment

Interesting projects, worth a look. But, to integrate them in my current c# project looks like a project on its own :-)
0

I suggest to approaches:

1) Tokenise using string.Split and match against a Dictionary of keys you have

2) Implement tokeniser yourself a reader with ReadToken() method which it adds the characters to a buffer until it finds (Split could be doing that) a split character and outputs that as token. Then you check against your dictionary.

Improve this answer

2 Comments

Tokenizing isn't possible since some of the chars that might be used as separators are part of keywords. Even if I tokenize the string into words, the keyword can still occur somewhere withing the word.
Your examples did not convey that. True they are used for the end of the word (e.g. "Schw.") but not in the middle of the word - unless there are such cases that you have not shared.
0

Maybe it's a little overpowered but you should definitely take a look at ANTLR.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.