Are there any algorithms for splitting or combining words into their more common form?

Question

Are there any existing algorithms which can look through a list of words and split or combine words into their more common form?

For example, I have a list of many business names in the health care industry. The word "healthcare" is often written "health care". There are also business names which might be split or combined, such as "Walmart" and "Wal mart".

Are there any algorithms which can look at my list of words and identify that "healthcare" is more often written as two words, and that "Wal mart" is more often written as a single word?

I'm looking for the names of existing algorithms (which can help when searching the web), or links to existing white-papers or blog posts.

I'd prefer an algorithm that doesn't depend on a dictionary or other external list of words or business names.

EDITS:

Background:

I already have some code that is moderately successful at this task. The code was thrown together without much rigor. I hoped there were some established algorithms, which would likely be more academic and complete then what I've come up with. This question is not about the method I've come up with, but saying "it's impossible" doesn't convince me.

Clarification:

The "more common form" of a word is the way the word(s) are most often written. For example, "Walmart" appeared many times, and "Wal mart" appeared many times, but "Walmart" appeared more often then "Wal mart" and so "Walmart" is the "more common form" of the word.

I don't expect this algorithm to produce perfect results. Like any machine learning problem, I expect the results to be dependent on the quality of data I give it, and how much data I have.

Answer 1

Generally I think you are after linguistic normalization and the algorithms that are applicable to your description of the problem are the algorithms that solve the problem of polysemy and collocations in particular.

The word "healthcare" is often written "health care" ...

The accepted defintion for collocations is a combination of adjacent words that have a common meaning. The hypernym of "health care" and "healthcare" is social insurance for the ill and injured, this is coincidently is also a related hypernym for "medicare" (though they are not exactly the same, but I presume you are interested in business names that could mention all the above).

The WordNet lexical database is one of the largest and you can use its search facilities to explore collocations and hypernyms.

The hypernyms, collocations and the semantic relationships are typically aggregated in a database, and I am unconvinced that,

... an algorithm that doesn't depend on a dictionary or other external list of words or business names.

is a viable approach. In the best case you would be essentially eschewing the shoulders of giants and slowly re-building what's already available in existing lexical databases and collocation dictionaries as your algorithms accumulates and stores the interpretation of the collocations you encounter in your tasks.

Here are some additional resources and links,

• Oxford Collocation dictionary (1, 2)
• BBI Dictionary of English Word Combinations
• EuroWordNet
• Longman Collocations Dictionary and Thesaurus

For locating the necessary reasearch papers and algorithms I suggest that you simply employ citeseer with collocations as the main term, it is fairly unique to natural language processing. I am not sure though as I expressed above that you will be able to find an online algorithm that doesn't rely on dictionaries or pre-existing learning corpora for your task.

Answer 2

One way to solve it is to use the Levenshtein Edit Distance Algorithm.

Basically you take whatever string was entered, and then you compute the LED value of every word or phrase that starts with the same letter in your corpus (dictionary). The one with the lowest value is the "proper" form of the word or phrase. It's rare for someone to mistype the first letter of a word, so this approach works pretty well if you've got a decent corpus to work from. There are other related algorithms that may work slightly better or worse depending on what you're matching, but I've used LED for fuzzy string searches for many years, and I've always been fairly impressed with how well it works. I didn't quite follow what your input data was like, so it may or may not work if you don't have reliable word boundaries, though you may be able to modify LED a bit to get it to work even without good word boundaries (maybe one pass treating all existing word boundaries as if they're reliable, and then another pass through with a sliding window of two "words" at a time. If you get a lower LED on the combination than you get for the sum of the two words, then use the combination or something.

Anyway, it's an interesting puzzle. I suspect whatever you come up with will probably use some variant of LED.

Answer 3

A quick search for "common compound words" revealed a few sites like this:

http://www.learningdifferences.com/Main%20Page/Topics/Compound%20Word%20Lists/Compound_Word_%20Lists_complete.htm

The problem here is that not all ("notall"?) compound words are legal. So at least, a validation check would require a lookup of each of the pieces against a dictionary (easy), a lookup of the compound word against a dictionary (easy), and a lookup against your list of validated compound words (easy). The missing piece is a confirmed mapping between the legal compound words and its pieces.

To split:

• lookup the work in the compound words list, then iterate through each possible split & lookup each piece in a dictionary: ("n otall", "no otall", "not all", ...) to determine the split.

To join:

• just concantenate & then lookup in a dictionary & in the legal words list.

In the long run, you might end up using a sort of Markov chain & Bayesian probability to determine the likelihood of an appropriate split, and slowly over time add to the "common" list of words with the ones you consider legal.

Or more simply, each time you see a word that cleanly splits into two words in the dictionary, add a mapping entry between the word and those pieces. There will often be more than one for a word. After that, each time you see that compound word again, give each of its mappings a "yes" vote. Each time you see the pieces separately, add a "no" vote to that mapping. Over time, you'd build up a list of mappings with a sense of the probability of it appearing in use.

I don't know know how large that list would get; in English, I doubt it would really grow to be that large. And you'd only have to create a legal compound-to-split mapping once.

...

If you had a mapping between compound and split, and carried values for "compound count" and "split count" for each mapping item, then the probability that the compound usage is prevalent is just compound_usage / sum(compound_usage + split_usage). You could leverage this the probabilistic way by generating a uniform random, and if less than that probability, print the compound, otherwise print the split version. Or you could just set a threshold (say 80%) and use some Bayesian smoothing to account for low frequency items.

Ultimately, there's nothing in the language that determines if a compound is "correct" -- it's convention and usage. It probably even varies regionally. So one way or another you're going to have to use some sort of sampling / probability estimation process to build a dictionary of compound words.

(Actually that sounds like kind of a fun project; I may play around with that.)

...

Since building the mapping would be a one-time task for each compound word, another alternative would be to farm the verification of the compounds & splits out to the Mechanical Turk: https://www.mturk.com/mturk/welcome Ultimately, that might be easier than trying to train and tune a fancier ML algorithm that really just needs to run once for each possible combination.

Answer 4

Not that I'm an expert, but you could use a corpora like google does, and just use the statistics of words that are found in the internet.

For example, if there are 100K occurrences of Wallmart in the WWW and only 10K "wall mart" you would know that it's probably best to use the first one.

Answer 5

What David Everlöf said in the comment is actually not a too bad suggestion. More generally, if your application has internet access, it may be a good idea to see if you can make it consult online resources.

To stick with google, it is not hard to send a http request which performs a google search on the word you are examining. Then extract the suggestion part ('did you mean: Wallmart?') from the html document that is returned (if existent) and correct your word based on that suggestion.

Answer 6

You can always tell if two words are mashed together because there will be two consonants next to each other that are not part of a slide and are not the same. Slides are consonant combinations like st, dr, and th. If there are three consonants or more, you know it is two combined words. The two words can be divided between the slide and consonant or the two slides if there is four consonants. If there is two consonants, it is either a slide, two of the same letters, like ll, or combined words. Dividing it into two words would then be trivial.