2
$\begingroup$

I have a huge list of strings. The goal is to make a database of "relevant" words.

Of course in the context of what I work with, "relevance" is something akin to the organization I work with. For e.g. if it is a automobile manufacturing industry they'd buy products like

Automotive assembly equipment
Radial tyres
Etc

If it were an aircraft manufacturing industry:

Fabricated Aluminium Body
Hydraulic Fluid
Skydrol
Jet Fuel
Etc...

Issue is that I might come across so many spelling mistakes, abbreviations, and variations.

So what is a technique I can prepare a database of words like these when I have nothing to start with, except a huge list of strings.

$\endgroup$
  • 2
    $\begingroup$ Read about TF/IDF . $\endgroup$ – Erel Segal-Halevi Oct 29 '13 at 7:44
5
$\begingroup$

This is still an open problem. You can use some techniques like Stemming the words of the strings and counting them called Bag of Words Approach. Most occurring words comes most of the time are in your relevant words list.

However, you would find that non-informative words like 'the', 'is' are coming most of the time in the answer. Simplest way would be to create a dictionary of stop words of english or of the language that would include words that can be discarded. It can contain prepositions, conjunctions, pronouns, articles or may be frequent verbs, as according to your requirements. You can use a Trie for creating this fast lookup dictionary.

However, there is another approach that would find the words that are most occuring. It is called TF/IDF. This is used when you have different documents/strings to compare to each other. It gives you a value for each word that would be proportional to how much it occurs in this document but not in other documents. So words like 'the', 'is' would have comparatively less value. However, if your strings have words like Aluminium in most of them, it would also be having low value. so use it with caution.

Another thing that i would like to point out about the use of TF/IDF is that you would have to divide your data into some parts, to compare to each other. TF/IDF would give result for each of these parts. Lets say if you take each of your string as one part, then it would give you a huge set of key-words since you have a huge set of strings. It would be better to randomly partition your huge-set-of-strings into say 2 or 4 or 8 parts and then find keywords for each part and then take either intersection or union.

The trick is to use different methods and use one that gives the best results.

For spelling mistake you can create a BKTree, that would allow you to find how much two words differ in their spelling mistakes. If you add this approach, it can give you better or worse results. For e.g. if you allow words with one difference acceptable, it would treat bat and cat the same. But it would also take care of Aluminium and Allminium.

$\endgroup$
  • $\begingroup$ @D>W. yaa you are right. but it can be counterproductive too ( if some important words is in most of the document and also in small number in each document). Sometimes creating a list of stop words can be better. but O.P. should check out what is better for him. $\endgroup$ – Ashish Negi Oct 30 '13 at 5:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.