1

I would like to connect letters into meaningful words? E.g.

input:

T E ST IN G WE B A P P LIC AT IO N S 

output:

TESTING WEB APPLICATIONS
  • what kind of task is this? A task in NLP, or just some string operation? What kinds of NLP task(s) are involved?

  • Are there software programs that I can use to do the job?

  • What are some programming libraries that I can call to do the job?

note that: my original text not shown here is a mixture of space-separated letters and words, and are there software programs or programming libraries that can find out and take advantage of the existing words?

10
  • 1
    This almost sounds like a tool recommendation, which would be off-topic. If you want to write something like this yourself, you need a big list of valid words, and then we can talk about substring search algorithms. If you actually want the program to choose "meaningful" words instead of whatever comes up first in the list, that requires natural language processing, which is still a largely unsolved problem. Which of these issues are you actually seeking help for?
    – Ixrec
    Commented Feb 15, 2015 at 13:06
  • Is the first "issue" a method for solving the second "issue" (an NLP problem)? yes, I would like to learn what is on topic here.
    – Tim
    Commented Feb 15, 2015 at 13:38
  • This is language modeling. A language model takes a sequence of words and returns a score for how likely that phrase is in the language. An appropriate language model (such as a smoothed trigram) and a dynamic programming algorithm like Viterbi can make this relatively computationally efficient. Considering taking a look at the first couple lectures of Michael Collins' NLP Coursera.
    – chmullig
    Commented Feb 15, 2015 at 14:59
  • @chmullig: Are there software programs that I can use to do the job? What are some programming libraries that I can call to do the job? (note that: my original text not shown here is a mixture of space-separated letters and words, and are there software programs or programming libraries that can find out and take advantage of the existing words?)
    – Tim
    Commented Feb 15, 2015 at 18:53
  • You need to provide more context. Do you want all solutions? Is this intended to solve some kind of puzzle or is there more context (e.g. surrounding words) from a natural language application? Commented Feb 15, 2015 at 23:50

4 Answers 4

23

You definitely need NLP. For example:

EX P ER T S E XC H A NG E

may either mean

EXPERT SEX CHANGE

or

EXPERTS EXCHANGE

depending on context.

10
  • Can proof reading software such as aspell solve the problem somehow?
    – Tim
    Commented Feb 15, 2015 at 13:23
  • 12
    They are both spelled correctly, so, obviously not. Commented Feb 15, 2015 at 13:24
  • What is the kind of task(s) involved in my question called in NLP?
    – Tim
    Commented Feb 15, 2015 at 13:37
  • 5
    @lesto, even a human with context won't be able to find the correct spelling sometimes. Commented Feb 15, 2015 at 16:06
  • 1
    Well, you need NLP for the rare cases where this type of multiple solution/interpretation is possible, presuming only one solution is "right", but the OP says nothing of the sort; perhaps he wants all solutions, e.g. this is a puzzle? I think fundamentally the problem is combinatorial, selecting the "right" answer comes after that. Commented Feb 15, 2015 at 23:49
11

This problem is called word segmentation or text segmentation, and it has been extensively studied.

Note that in languages such as Chinese, Japanese, and Korean, all text in a sentence normally appears with no whitespace. Word segmentation is therefore a prerequisite for machine interpretation of CJK text.

2
5

Actually this is not an AI problem, this is pure programming question solved by dynamic programming.

If you simply want to connect the tokens into a list of correctly spelled words then you proceed as follows (Top down style dynamic programming):

public class Connector {

    public static void main(String[] args) {

        List<String> tokens = new ArrayList<String>(); // input
        Connector connector = new Connector();

        @SuppressWarnings("unused")
        List<String> ret = connector.connect(tokens);
    }

    Map<Integer, List<String>> cache;
    List<String> tokens;

    public List<String> connect(List<String> tokens) {
        this.cache = new HashMap<Integer, List<String>>();
        this.tokens = tokens;
        List<String> ret = connect(tokens, 0);
        return ret;
    }


    List<String> connect(List<String> tokens, int start) {
        if (cache.containsKey(start)) {
            return cache.get(start);
        } else {
            List<String> results = new ArrayList<String>();
            connectHelper(tokens, start, results);
            cache.put(start, results);
            return results;
        }
    }


    void connectHelper(List<String> tokens, int start, List<String> results) {
        int n = tokens.size();
        for(int i = start + 1; i < n; i++) {
            String part = concat(tokens, start, i);
            if (dictContains(part)) {
                List<String> restParts = connect(tokens, i);
                for(String oneRestPart : restParts) {
                    results.add(part + " " + oneRestPart);
                }
            }
        }
    }

    static private String concat(List<String> tokens, int low, int hi) {
        StringBuilder sb = new StringBuilder();
        for(int i = low; i < hi; i++) {
            sb.append(tokens.get(i));
        }
        return sb.toString();
    }
}
6
  • 3
    In the example from my answer, how does your algorithm decide which one of the two possible solutions is the correct one? Commented Feb 15, 2015 at 14:16
  • 3
    @JörgWMittag: Does it need to? The question doesn't specify that the software needs to produce correct result. Only meaningful results. So the correct answer to your answer would be to print both results.
    – slebetman
    Commented Feb 15, 2015 at 14:28
  • 2
    @slebetman: I guess it depends on whether you interpret "meaningful" as "meaningful in context" or simply "individual meaningful words". Commented Feb 15, 2015 at 16:00
  • Thanks. Where is the part in the code that can recognize a sequence of letters as a word? Does it need some human used dictionary?
    – Tim
    Commented Feb 15, 2015 at 18:51
  • @Tim. Yes, it's the dictContains(part) bit. It checks if the word exists in the dictionary. It's not shown how that's implemented. What's shown is how the parts are combined in various combinations and those combinations are checked against the dictionary.
    – slebetman
    Commented Feb 16, 2015 at 1:33
2

The problem is called 'language modeling'

It is trivial to connect letters into some words by taking any dictionary (list of valid words) and finding a way that fits. However, in practice the main problem in this task usuall is finding the best words that fit those letters. Fortunately, this is a problem that others have as well - it occurs in, for example, speech recognition and thus is rather well researched and has resources and various ways to try and solve it. In this field, this problem is generally called 'language modeling'.

Statistical methods

The currently standard approach for this problem is to statistically evaluate the likelihood of each subfragment based on a large number of examples of how the language looks in real world. If we often see fragments like "... to therapist" and rarely see fragments like "... to the rapist" then we may assume that those letters should be merged together.

A good classic textbook descriptions are available in Speech and Language Processing by Dan Jurafsky and Jim Martin (chapter 6 in the 1st edition, chapter 4 in the 2nd edition) and Foundations of Statistical Natural Language Processing by Chris Manning and Hinrich Schütze (chapter 6).

An often used library for doing language modeling is SRILM - http://www.speech.sri.com/projects/srilm/manpages/ and I believe that projects such as python NLTK (http://www.nltk.org/) also have tools for that. In any case, the particular model (weights of word combinations) is different for each language and domain, so this may be something that you have to adapt yourself.

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