Существуют ли какие-нибудь умно эффективные алгоритмы для вычисления в пространстве разбиений строки?

Question

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

Например, если строка 'abc', то будут вероятности для 'a', 'b', 'c', 'ab,' bc 'и' abc '. Существует четыре возможных разбиения строки: «abc», «ab | c», «a | bc» и «a | b | c». Алгоритм должен найти произведение вероятностей компонентов для каждого разбиения, а затем сложить четыре результирующих числа.

В настоящее время я написал итератор python, который использует двоичные представления целых чисел для разделов (например, 00, 01, 10, 11 для примера выше) и просто просматривает целые числа. К сожалению, это очень медленно для строк длиной более 20 символов.

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

В ответ на некоторые комментарии приведем дополнительную информацию:
Строка может содержать что угодно, например, "foobar (foo2)" - наш алфавит состоит из строчных букв, цифр и всех трех типов скобок ("(", "[", "{"), дефисов и пробелов.
Цель состоит в том, чтобы получить правдоподобие строки с учетом вероятностей отдельных слов. Таким образом, L (S = 'abc') = P ('abc') + P ('ab') P ('c') + P ('a') P ('bc') + P ('a') P ('b') P ('c') (Здесь "P ('abc')" указывает вероятность слова "abc", а "L (S = 'abc')" - статистическая вероятность наблюдения. строка 'abc').

Answer 1

A Динамическое программирование решение (если я правильно понял вопрос):

def dynProgSolution(text, probs):
  probUpTo = [1]
  for i in range(1, len(text)+1):
    cur = sum(v*probs[text[k:i]] for k, v in enumerate(probUpTo))
    probUpTo.append(cur)
  return probUpTo[-1]

print dynProgSolution(
  'abc',
  {'a': 0.1, 'b': 0.2, 'c': 0.3,
   'ab': 0.4, 'bc': 0.5, 'abc': 0.6}
  )

Сложность O (N ² ), поэтому она легко решит проблему для N = 20.

Как, почему это работает:

• Все, что вы умножите на probs['a']*probs['b'], вы также умножите на probs['ab']
• Благодаря Распределительному свойству умножения и сложения, вы можете сложить эти два значения вместе и умножить эту единственную сумму на все ее продолжения.
• Для каждой возможной последней подстроки, она добавляет сумму всех разбиений, заканчивающихся тем, добавляя ее вероятность, умноженную на сумму всех вероятностей предыдущих путей. (приветствуется альтернативная формулировка. мой питон лучше моего английского ..)

Answer 2

Во-первых, профиль, чтобы найти узкое место.

Если узким местом является просто огромное количество возможных разделов, я рекомендую распараллеливание, возможно, через multiprocessing. Если этого еще недостаточно, вы можете заглянуть в кластер Beowulf .

Если узким местом является только то, что вычисления медленны, попробуйте обстреливать C. Это довольно легко сделать с помощью ctypes.

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

Answer 3

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

рассмотрим длинную строку, например 'abcdefghik', длиной 10, для определенности без потери общности. При наивном подходе вы умножаете p (a) на множество разделов хвоста 9, p (ab) на множество разделов хвоста 8 и т. Д .; в частности, p (a) и p (b) будут умножать те же самые разбиения 8-хвоста (все они), что и p (ab) - 3 умножения и две суммы среди них. Таким образом, коэффициент:

(p(ab) + p(a) * p(b)) * (partitions of the 8-tail)

и мы получили 2 умножения и 1 сумму для этой части, сохранив 1 продукт и 1 сумму. чтобы покрыть все разделы с точкой разделения справа от 'b'. Когда дело доходит до разделов с разделением справа от 'c',

(p(abc) + p(ab) * p(c) + p(a) * (p(b)*p(c)+p(bc)) * (partitions of the 7-tail)

экономия средств, отчасти благодаря внутреннему рефакторингу - хотя, конечно, нужно быть осторожным с двойным счетом. Я думаю, что этот подход может быть обобщен - начните с середины и рассмотрите все разделы, которые там разделены, отдельно (и рекурсивно) для левой и правой части, умножения и суммирования; затем добавьте все разделы, которые там не разбиты, например, в этом примере половинками являются «abcde» слева и «fghik» справа, вторая часть посвящена всем разделам, где «ef» вместе, а не друг от друга, поэтому «сверните» все вероятности, посчитав, что «ef» 'как новый' superletter 'X, и у вас осталась строка на одну короче,' abcdXghik '(конечно, вероятности для подстрок THAT отображаются непосредственно в оригиналы, например, p (cdXg) в новой строке просто в точности p (cdefg) в оригинале).

Answer 4

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

Я понимаю, что вы используете Python, но ... как примечание, которое может быть интересным, если вы делаете это на Perl, вам даже не нужно писать какой-либо код; встроенный модуль Memoize сделает кеширование за вас!

Answer 5

Вы должны заглянуть в модуль itertools. Он может создать генератор для вас очень быстро. Учитывая вашу входную строку, он предоставит вам все возможные перестановки. В зависимости от того, что вам нужно, есть также генератор combinations(). Я не совсем уверен, смотрите ли вы на «b | ca», когда смотрите «abc», но в любом случае этот модуль может оказаться полезным для вас.