python – 文本分段：将输入与字典中最长的单词匹配的算法

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

因此,在此示例中有两个解决方案,但我们希望使用最长的单词选择解决方案,即我们希望使用深度优先搜索策略从右侧探索树.

所以我们的算法应该：

>按降序长度排序字典.
>查找当前字符串的所有前缀.如果没有,则返回False.
>将前缀设置为最长的未探索前缀.
>将其从字符串中删除.如果字符串为空,我们找到了一个解决方案,返回所有前缀的列表.
>递归到2.
>此分支失败,返回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,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),pref)
            if res:
                res.append(token)
                return res
    # Not possible
    return False

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