Разбивая строку на последовательность слов - PullRequest
Новая
       12

Разбивая строку на последовательность слов

13 голосов
/ 25 августа 2011

Недавно я наткнулся на следующий вопрос интервью:

Учитывая входную строку и словарь слов, реализуйте метод, который разбивает входную строку на разделенную пробелами строку слов словаря, котораяпоисковая система может использовать для "Вы имели в виду?"Например, ввод «яблочный пирог» должен давать вывод «яблочный пирог».

Кажется, я не могу найти оптимальное решение в том, что касается сложности.У кого-нибудь есть предложения, как это сделать эффективно?

Ответы [ 5 ]

10 голосов
/ 27 августа 2011

Похоже, вопрос касается именно моей проблемы с собеседованием, вплоть до примера, который я использовал в посте на The Noisy Channel.Рад, что вам понравилось решение.Я совершенно уверен, что вы не можете превзойти решение для динамического программирования / запоминания O (n ^ 2), которое я описываю для наихудшей производительности.

Вы можете добиться большего успеха на практике, если ваш словарь и ввод не являются патологическими.Например, если вы можете идентифицировать в линейном времени подстроки входной строки в словаре (например, с помощью дерева), и если число таких подстрок является постоянным, то общее время будет линейным.Конечно, это много предположений, но реальные данные часто намного лучше, чем патологический наихудший случай.

Существуют также забавные варианты задачи, которые усложняют задачу, например, перечисление всех допустимых сегментаций, выводнаилучшая сегментация, основанная на некотором определении best, обработка словаря, слишком большого для размещения в памяти, и обработка неточной сегментации (например, исправление орфографических ошибок).Не стесняйтесь комментировать мой блог или иным образом связаться со мной, чтобы следить.

8 голосов
/ 25 августа 2011

Эта ссылка описывает эту проблему как идеальный вопрос для интервью и предоставляет несколько способов ее решения.По существу, это включает рекурсивный возврат .На этом уровне это приведет к сложности O (2 ^ n).Эффективное решение, использующее запоминание, могло бы довести эту проблему до O (n ^ 2).

1 голос
/ 24 декабря 2015

Используя python, мы можем написать две функции, первая из которых segment возвращает первую сегментацию фрагмента смежного текста на слова по заданному словарю или None, если такая сегментация не найдена. Другая функция segment_all возвращает список всех найденных сегментаций. В худшем случае сложность O (n ** 2), где n - длина входной строки в символах.

Представленное здесь решение может быть расширено, чтобы включить исправления орфографии и анализ биграмм для определения наиболее вероятной сегментации. 

def memo(func):
    '''
    Applies simple memoization to a function
    '''
    cache = {}
    def closure(*args):
        if args in cache:
            v = cache[args]
        else:
            v = func(*args)
            cache[args] = v
        return v
    return closure


def segment(text, words):
    '''
    Return the first match that is the segmentation of 'text' into words
    '''
    @memo
    def _segment(text):
        if text in words: return text
        for i in xrange(1, len(text)):
            prefix, suffix = text[:i], text[i:]
            segmented_suffix = _segment(suffix)
            if prefix in words and segmented_suffix:
                return '%s %s' % (prefix, segmented_suffix)
        return None
    return _segment(text)


def segment_all(text, words):
    '''
    Return a full list of matches that are the segmentation of 'text' into words
    '''
    @memo
    def _segment(text):
        matches = []
        if text in words: 
            matches.append(text)
        for i in xrange(1, len(text)):
            prefix, suffix = text[:i], text[i:]
            segmented_suffix_matches = _segment(suffix)
            if prefix in words and len(segmented_suffix_matches):
                for match in segmented_suffix_matches:
                    matches.append('%s %s' % (prefix, match))
        return matches 
    return _segment(text)


if __name__ == "__main__":    
    string = 'cargocultscience'
    words = set('car cargo go cult science'.split())
    print segment(string, words)
    # >>> car go cult science
    print segment_all(string, words)
    # >>> ['car go cult science', 'cargo cult science']
0 голосов
/ 01 апреля 2015

import java.util. *; 

class Position {
    int indexTest,no;
    Position(int indexTest,int no)
    {
        this.indexTest=indexTest;
        this.no=no;
    } } class RandomWordCombo {
    static boolean isCombo(String[] dict,String test)
    {
        HashMap<String,ArrayList<String>> dic=new HashMap<String,ArrayList<String>>();
        Stack<Position> pos=new Stack<Position>();
        for(String each:dict)
        {
            if(dic.containsKey(""+each.charAt(0)))
            {
                //System.out.println("=========it is here");
                ArrayList<String> temp=dic.get(""+each.charAt(0));
                temp.add(each);
                dic.put(""+each.charAt(0),temp);
            }
            else
            {
                ArrayList<String> temp=new ArrayList<String>();
                temp.add(each);
                dic.put(""+each.charAt(0),temp);
            }
        }
        Iterator it = dic.entrySet().iterator();
    while (it.hasNext()) {
        Map.Entry pair = (Map.Entry)it.next();
        System.out.println("key: "+pair.getKey());
        for(String str:(ArrayList<String>)pair.getValue())
        {
            System.out.print(str);
        }
    }
        pos.push(new Position(0,0));
        while(!pos.isEmpty())
        {
            Position position=pos.pop();
            System.out.println("position index: "+position.indexTest+" no: "+position.no);
            if(dic.containsKey(""+test.charAt(position.indexTest)))
            {
                ArrayList<String> strings=dic.get(""+test.charAt(position.indexTest)); 
                if(strings.size()>1&&position.no<strings.size()-1)
                     pos.push(new Position(position.indexTest,position.no+1));
                String str=strings.get(position.no);
                if(position.indexTest+str.length()==test.length())
                    return true;
                pos.push(new Position(position.indexTest+str.length(),0));
            }
        }
        return false;
    }
    public static void main(String[] st)
    {
        String[] dic={"world","hello","super","hell"};
        System.out.println("is 'hellworld' a combo: "+isCombo(dic,"superman"));
    } }

Я сделал похожую проблему.Это решение дает true или false, если данная строка является комбинацией словарных слов.Это может быть легко преобразовано, чтобы получить разделенную пробелами строку.Его средняя сложность составляет O (n), где n: нет словарных слов в данной строке.

0 голосов
/ 25 августа 2011

Один из вариантов - хранить все допустимые английские слова в дереве. После того, как вы это сделаете, вы можете начать идти с дерева вниз от корня, следуя буквам в строке. Всякий раз, когда вы найдете узел, помеченный как слово, у вас есть два варианта:

  1. Прервать ввод в этой точке или
  2. Продолжайте расширять слово.

Вы можете утверждать, что нашли совпадение после того, как разбили входные данные на набор слов, которые все являются допустимыми и не имеют оставшихся символов. Поскольку в каждой букве у вас есть либо одна принудительная опция (либо вы создаете слово, которое является недопустимым и должно быть остановлено - или вы можете продолжать расширять слово), либо две опции (разделение или продолжение), вы можете реализовать эту функцию с использованием исчерпывающей рекурсии: 

PartitionWords(lettersLeft, wordSoFar, wordBreaks, trieNode):
    // If you walked off the trie, this path fails.
    if trieNode is null, return.

    // If this trie node is a word, consider what happens if you split
    // the word here.
    if trieNode.isWord:
        // If there is no input left, you're done and have a partition.
        if lettersLeft is empty, output wordBreaks + wordSoFar and return

        // Otherwise, try splitting here.
        PartitinWords(lettersLeft, "", wordBreaks + wordSoFar, trie root)

    // Otherwise, consume the next letter and continue:
    PartitionWords(lettersLeft.substring(1), wordSoFar + lettersLeft[0], 
                   wordBreaks, trieNode.child[lettersLeft[0])

В патологически худшем случае в нем будут перечислены все разделы строки, которые не могут быть экспоненциально длинными. Однако это происходит только в том случае, если вы можете разбить строку огромным количеством способов, которые начинаются с правильных английских слов, и на практике это вряд ли произойдет. Если в строке много разделов, мы могли бы потратить много времени на их поиск. Например, рассмотрим строку «dotheredo». Мы можем разделить это многими способами: 

do the redo
do the red o
doth ere do
dot here do
dot he red o
dot he redo

Чтобы избежать этого, вы можете установить ограничение на количество ответов, о которых вы сообщаете, возможно, два или три.

Поскольку мы отключаем рекурсию, когда выходим из дерева, если мы когда-нибудь попробуем разделение, в котором оставшаяся часть строки не будет действительной, мы обнаружим это довольно быстро.

Надеюсь, это поможет!

...