Сегментация текста: Алгоритм для ввода ввода с самыми длинными словами из словаря

Question

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

thisisinsane => this is insane (correct as longest possible word from left) 
thisisinsane => this is in sane(wrong) 
Assuming 'this', 'is', 'in', 'insane' are all words in the dictionary. 

мне удалось решить эту проблему путем обхода с конца строки к началу сопрягая самое длинное слово можно. Но проблема начала кадрирование нас для подобных проблем ..

shareasale => share as ale(wrong as 'ale' not in the dictionary) 
shareasale => share a sale(correct) 
Assuming 'share', 'a', 'sale' are all words in the dictionary unlike 'ale'. 

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

shareasale => 'share' and 'as' (error = 'ale') 

и удалить их один раз из словаря и затем решить проблему. Таким образом,

shareasale => no valid segments when share is removed 
shareasale => share a sale (when 'as' is removed from the dictionary. 

Таким образом, мне тоже удалось решить эту проблему. Но тогда я не смог решить эту проблему

asignas => 'as' (error = 'ignas') 

Мое решение затем удалить «как» из словаря и попытаться решить

asignas => 'a' 'sign' (error = 'as') 

Поскольку в новом рекурсивном вызове «как» было удалено из словаря. Функция, которую я написал, - in this link. Я надеюсь, что кто-то сможет пройти через это и помочь мне найти лучший алгоритм для решения этой проблемы, предлагая модификацию моего существующего алгоритма.

Answer 1

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

     thisisinsane 
          | 
          | 
        (this)isinsane 
        /   \ 
        /   \ 
      (this,i)sinsane   (this,is)insane 
      /     /   \ 
      /     /   \ 
    (this,i,sin)ane   (this,is,in)sane (this,is,insane) 
           /
          /
         (this,is,in,sane) 

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

Таким образом, наш алгоритм должен:

1. Сортировка словаря по убыванию длины.
2. Найти все префиксы текущей строки. Если их нет, верните False.
3. Установить prefix в самый длинный неисследованный префикс.
4. Удалить его из строки. Если строка пуста, мы нашли решение, вернем список всех префиксов.
5. Recurse to 2.
6. Эта ветка не удалась, возвращается False.

---

Пример реализации этого решения:

def segment(string,wset): 
    """Segments a string into words prefering longer words givens 
    a dictionary wset.""" 
    # Sort wset in decreasing string order 
    wset.sort(key=len, reverse=True) 
    result = tokenize(string, wset, "") 
    if result: 
     result.pop() # Remove the empty string token 
     result.reverse() # Put the list into correct order 
     return result 
    else: 
     raise Exception("No possible segmentation!") 

def tokenize(string, wset, token): 
    """Returns either false if the string can't be segmented by 
    the current wset or a list of words that segment the string 
    in reverse order.""" 
    # Are we done yet? 
    if string == "": 
     return [token] 
    # Find all possible prefixes 
    for pref in wset: 
     if string.startswith(pref): 
      res = tokenize(string.replace(pref, '', 1), wset, pref) 
      if res: 
       res.append(token) 
       return res 
    # Not possible 
    return False 

print segment("thisisinsane", ['this', 'is', 'in', 'insane']) # this is insane 
print segment("shareasale", ['share', 'a', 'sale', 'as'])  # share a sale 
print segment("asignas", ['as', 'sign', 'a'])     # a sign as 

Answer 2

Просто сделайте рекурсивное сканирование, каждый раз добавляя единственное письмо к последнему слову (если оно находится в словаре), а также пытаетесь дать ему возможность начать новое слово. Это означает, что при каждом вызове у вас есть 1 или 2 гипотезы для тестирования (есть ли пробел или нет). Когда вы дойдете до конца ввода, и у вас есть правильный набор слов, сохраните это решение, если первое слово в нем больше, чем лучшее решение, которое вы нашли до сих пор.

Пример кода:

words=['share','as','a','sale','bla','other','any','sha','sh'] 
wdict={} 
best=[] 

def scan(input,i,prevarr): 
    global best 
    arr=list(prevarr) 
    # If array is empty, we automatically add first letter 
    if len(arr)<1: 
     arr.append(input[0:1]) 
     return scan(input,i+1,arr) 
    # If no more input is available, evaluate the solution 
    if i>=len(input): 
     # Is the last word a valid word 
     if wdict.has_key(arr[-1]): 
      # Is there a current best solution? 
      if len(best)==0: 
       best=arr  # No current solution so select this one 
      elif len(arr[0])>len(best[0]): 
       best=arr  # If new solution has a longer first word 
     return best 
    # If the last word in the sequence is a valid word, we can add a space and try 
    if wdict.has_key(arr[-1]): 
     arr.append(input[i:i+1]) 
     scan(input,i+1,arr) 
     del arr[-1] 
    # Add a letter to the last word and recurse 
    arr[-1]=arr[-1]+input[i:i+1] 
    return scan(input,i+1,arr) 

def main(): 
    for w in words: 
     wdict[w]=True 
    res=scan('shareasasale',0,[]) 
    print res 

if __name__ == '__main__': 
    main() 

Answer 3

алгоритм я бы использовал бы что-то вроде:

• ли ваш словарь сортируется путем уменьшения длины
• Построить функцию prefix(s) которая дает, в порядке, словарные слова, начинающиеся s
  • ie. prefix("informativecow") дает первое «информативными», а затем «информировать», а затем «информация», затем «в»
• Построить рекурсивную функцию test(s) которой:
  • если s пустая строка, возвращает Правда
  • для каждого префикса удалите префикс из s и вызовите test() с этой строкой. Если вы найдете то, что истинно, верните true. Если вы не нашли истины, верните False.

Answer 4

Для реального мира пример того, как сделать английский сегментации слов, посмотрите на источник Python wordsegment module. Это немного сложнее, потому что он использует таблицы частоты слов и фраз, но иллюстрирует подход memoization.

В частности, score иллюстрирует сегментацию подход:

def score(word, prev=None): 
    "Score a `word` in the context of the previous word, `prev`." 

    if prev is None: 
     if word in unigram_counts: 

      # Probability of the given word. 

      return unigram_counts[word]/1024908267229.0 
     else: 
      # Penalize words not found in the unigrams according 
      # to their length, a crucial heuristic. 

      return 10.0/(1024908267229.0 * 10 ** len(word)) 
    else: 
     bigram = '{0} {1}'.format(prev, word) 

     if bigram in bigram_counts and prev in unigram_counts: 

      # Conditional probability of the word given the previous 
      # word. The technical name is *stupid backoff* and it's 
      # not a probability distribution but it works well in 
      # practice. 

      return bigram_counts[bigram]/1024908267229.0/score(prev) 
     else: 
      # Fall back to using the unigram probability. 

      return score(word) 

Если вы заменили скор-функцию так, чтобы она вернулась более высокие оценки для более длинных матчей в словаре, то он будет делать, как вы хотите.