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?

closed as off-topic by Tulains Córdova, World Engineer Feb 24 '15 at 1:54

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions asking us to recommend a tool, library or favorite off-site resource are off-topic for Programmers as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it." – Tulains Córdova, World Engineer
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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 Feb 15 '15 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 Feb 15 '15 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 Feb 15 '15 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 Feb 15 '15 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? – Fizz Feb 15 '15 at 23:50
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.

  • Can proof reading software such as aspell solve the problem somehow? – Tim Feb 15 '15 at 13:23
  • 12
    They are both spelled correctly, so, obviously not. – Jörg W Mittag Feb 15 '15 at 13:24
  • What is the kind of task(s) involved in my question called in NLP? – Tim Feb 15 '15 at 13:37
  • 5
    @lesto, even a human with context won't be able to find the correct spelling sometimes. – Karolis Juodelė Feb 15 '15 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. – Fizz Feb 15 '15 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.

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();
    }
}
  • 3
    In the example from my answer, how does your algorithm decide which one of the two possible solutions is the correct one? – Jörg W Mittag Feb 15 '15 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 Feb 15 '15 at 14:28
  • 2
    @slebetman: I guess it depends on whether you interpret "meaningful" as "meaningful in context" or simply "individual meaningful words". – Jörg W Mittag Feb 15 '15 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 Feb 15 '15 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 Feb 16 '15 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.