парсинг слов в непрерывную строку

Question

Если есть строка со словами и без пробелов, как мне разобрать эти слова, если у меня есть словарь / список, содержащий эти слова?

Например, если моя строка "thisisastringwithwords", какМогу ли я использовать словарь для создания вывода "это строка со словами"?

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

Answer 1

Я предполагаю, что вы хотите эффективное решение, а не очевидное, когда вы неоднократно проверяете, начинается ли ваш текст со словарного слова.

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

РЕДАКТИРОВАТЬ: оказалось, что я заново изобретал попытки .

Answer 2

Я уже делал нечто подобное.Вы не можете использовать простой словарь.Результат будет грязным.Это зависит от того, нужно ли вам делать это только один раз или как целую программу.

Мое решение было:

1. Подключение к базе данных с рабочими словами из списка словарей (например, онлайн-словарь)
2. Фильтрация длинных и коротких слов в словареи проверьте, хотите ли вы обрезать материал (например, не используйте слова только с одним символом, например 'I' )
3. Начните с коротких слов и сравните вашу bigString со словарем базы данных.

Теперь вам нужно создать «таблицу возможностей».Потому что многие слова могут вписаться в 100%, но они неверны.Чем длиннее слово, тем больше уверенность в том, что это слово является правильным.

Это интенсивное использование процессора, но оно может работать точно в результате.Допустим, вы используете небольшой словарь из 10000 слов, и 3000 из них имеют длину 8 символов, вам нужно сравнить вашу bigString при запуске со всеми 3000 словами, и только если результат найден, он может перейти кследующее слово.Если в вашей большой строке 200 символов, вам нужно примерно (2000 символов / 8 средних символов) = минимум 250 полных циклов с сравнением.

Для меня я также сделал небольшую проверку слов с ошибками в сравнении.

пример процедуры (не копировать вставить)

    Dim bigString As String = "helloworld.thisisastackoverflowtest!"

    Dim dictionary As New List(Of String) 'contains the original words. lets make it case insentitive
    dictionary.Add("Hello")
    dictionary.Add("World")
    dictionary.Add("this")
    dictionary.Add("is")
    dictionary.Add("a")
    dictionary.Add("stack")
    dictionary.Add("over")
    dictionary.Add("flow")
    dictionary.Add("stackoverflow")
    dictionary.Add("test")
    dictionary.Add("!")


    For Each word As String In dictionary
        If word.Length < 1 Then dictionary.Remove(word) 'remove short words (will not work with for each in real)
        word = word.ToLower 'make it case insentitive
    Next

    Dim ResultComparer As New Dictionary(Of String, Double) 'String is the dictionary word. Double is a value as percent for a own function to weight result

    Dim i As Integer = 0 'start at the beginning
    Dim Found As Boolean = False
    Do
        For Each word In dictionary
            If bigString.IndexOf(word, i) > 0 Then
                ResultComparer.Add(word, MyWeightOfWord) 'add the word if found, long words are better and will increase the weight value 
                Found = True
            End If
        Next
        If Found = True Then
            i += ResultComparer(BestWordWithBestWeight).Length
        Else
            i += 1
        End If
    Loop

Answer 3

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

public static String[] StringToWords(String str, HashSet<string> words)
{      
  //Index of char - length of last valid word
  int[] bps = new int[str.Length + 1];

  for (int i = 0; i < bps.Length; i++)      
    bps[i] = -1;

  for (int i = 0; i < str.Length; i++)
  {
    for (int j = i + 1; j <= str.Length ; j++)
    {
      if (bps[j] == -1)
      {
        //Destination cell doesn't have valid backpointer yet
        //Try with the current substring
        String s = str.Substring(i, j - i);
        if (words.Contains(s))
          bps[j] = i;
      }
    }        
  }      

  //Backtrack to recovery sequence and then reverse 
  List<String> seg = new List<string>();
  for (int bp = str.Length; bps[bp] != -1 ;bp = bps[bp])      
    seg.Add(str.Substring(bps[bp], bp - bps[bp]));      
  seg.Reverse();
  return seg.ToArray();
}

Создание hastset со списком слов из / usr / share / dict / words и тестирование с помощью

foreach (var s in StringSplitter.StringToWords("thisisastringwithwords", dict))
    Console.WriteLine(s);

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

Существуют более сложные методы, которые используют конечные автоматы и языковые модели.которые могут генерировать несколько сегментов и применять вероятностное ранжирование.

Answer 4

Хорошо, я попытаюсь сделать это вручную. Идеальная (ish) структура данных для вашей задачи (как вы уже сказали) состоит из слов в словаре. Три лучше всего визуализировать как DFA , хороший конечный автомат, в котором вы переходите от одного состояния к другому для каждого нового персонажа. Это действительно легко сделать в коде, класс стиля Java (ish) для этого будет:

Class State 
{
   String matchedWord;
   Map<char,State> mapChildren;
}

С этого момента построить дерево очень просто. Это как иметь корневую древовидную структуру, в которой каждый узел имеет несколько дочерних элементов. Каждый ребенок посещается по одному символу перехода. Использование структуры типа HashMap сокращает время простоя для поиска символа для следующих State отображений. С другой стороны, если бы у вас было всего 26 символов для алфавита, то fixed size array of 26 также помог бы.

Теперь, если все это имеет смысл, у вас есть три, ваша проблема все еще не полностью решена. Здесь вы начинаете делать то же самое, что и движки регулярных выражений, проходя по дереву, отслеживая состояния, соответствующие целому слову в словаре (это то, что у меня было matchedWord в структуре State), используйте некоторая логика возврата для перехода в предыдущее состояние матча, если текущий трейл зашел в тупик. Я знаю его общее, но, учитывая структуру дерева, все остальное довольно просто.

Answer 5

Это именно та проблема, с которой приходится сталкиваться при программном анализе языков, таких как китайский, где между словами нет пробелов.Один из методов, который работает с этими языками, - это начать с разделения текста на знаки препинания.Это дает вам фразы.Затем вы перебираете фразы и пытаетесь разбить их на слова, начиная с длины самого длинного слова в вашем словаре.Допустим, длина составляет 13 символов.Возьмите первые 13 символов из фразы и посмотрите, есть ли она в вашем словаре.Если это так, примите это как правильное слово сейчас, продвиньтесь во фразе и повторите.В противном случае сократите подстроку до 12 символов, затем до 11 символов и т. Д.

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

words with string a Isis th

Сначала слово Isis (египетская богиня) кажется правильным.Однако, когда вы обнаружите, что «th» отсутствует в вашем словаре, вы знаете, что поблизости есть проблема сегментации слов.Решите это, перейдя к результату прямой сегментации «this» для невыровненной последовательности «thisis», так как оба слова находятся в словаре.

Менее распространенный вариант этой проблемы - когда смежные слова разделяют последовательностькоторый может пойти в любую сторону.Если у вас была последовательность вроде «archand» (чтобы придумать что-то), должна ли она быть «arc hand» или «arch and»?Способ определения - применить проверку грамматики к результатам.В любом случае это должно быть сделано для всего текста.

Answer 6

Я говорил вам, что это кажется невыполнимой задачей.Но вы можете взглянуть на связанный с этим вопрос - он может вам помочь.

Answer 7

Если вы уверены, что в словаре есть все слова фразы, вы можете использовать этот алгоритм:

String phrase = "thisisastringwithwords";
String fullPhrase = "";
Set<String> myDictionary;
do {
    foreach(item in myDictionary){
        if(phrase.startsWith(item){
            fullPhrase += item + " ";
            phrase.remove(item);
            break;
        }
    }
} while(phrase.length != 0);

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