Как я могу найти вероятные вхождения подстрок внутри другой строки?

Question

Скажите, у меня есть коллекция строк:

• конституция
• абракадабра
• холодильник
• stackoverflow

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

Какой алгоритм мог бы помочь мне найти наиболее вероятные вхождения строк из коллекции в поврежденном предложении?

Вот пример ввода:

xbracadabrqbonstitution ibracadabrefrigeratos obracadabri xtackoverflotefrigeratos

Исходя из этого, я ожидал, что смогу восстановить этот массив известных слов:

['abcracadabra',' конституция ',' абракадабра ',' холодильник ',' абракадабрия ',' stackoverflow ',' холодильник ']

предложения довольно короткие (обычно 5-6 слов), поэтому яможет позволить себе алгоритмы, требующие памяти и энергииКроме того, повреждение всегда ограничивается несколькими первыми и последними символами каждого слова;середина всегда правильная (вот почему я ищу большие подстроки).

Есть идеи?Поскольку слова четко не разделены, обычное расстояние редактирования не позволяет.

Answer 1

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

Для каждой подстроки вы можете просто найти ее в предложении, а если это произойдет, вы можете пометить ее как возможную часть предложения. Для скорости вам может потребоваться выполнить поиск по предложению в O (n) (например, используя KMP или Rabin Karp )

Вот простой способ взломать идею в Python (используя сопоставление строк методом грубой силы):

d=["constitution","abracadabra","refrigerator","stackoverflow"]

def substring_match(word,sentence,min_length):
    for start in xrange(0,len(word)):
        for end in xrange(start+min_length,len(word)):
            substr=word[start:end+1]
            if substr in sentence:
                return True
    return False

def look_for_words(word_dict,sent_word):
    return [word for word in word_dict if substring_match(word,sent_word,5)]

def look(word_dict,sentence):
    ret=[]
    for word in sentence.split():
        ret.extend(look_for_words(word_dict,word))
    return ret

if __name__=='__main__':
    print "\n".join(look(d,"xbracadabrqbonstitution ibracadabrefrigeratos obracadabri xtackoverflotefrigeratos"))

Answer 2

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

Во-первых, вам нужна любая эвристическая функция f, которая берет слово w и возвращает ближайшее слово или не соответствует.

Тогда вы просто генерируете множество всех возможных w в вашей строке. В худшем случае это означает, что нужно взять набор всех строк длины 1, затем длины 2, затем длины 3 до длины вашей строки. Общее число сгенерированных таким образом w будет около (n * n-1) / 2

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

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

Answer 3

Вы можете попробовать Алгоритм расстояния Левенштейна , чтобы найти слова с минимальным расстоянием до слов в вашем словаре (вы определяете толерантность).

Удачи!