Java или Python регулярное выражение поиска большого списка слов

Question

У меня есть список "Nw" английских слов, которые я хотел бы найти, используя "Ne", различные регулярные выражения. Nw - несколько сотен тысяч записей, а Ne - несколько сотен. Регулярные выражения допускают только замену отдельных символов, то есть регулярные выражения содержат только «символы слова» (\w) или ? (возможно более одного). Я хотел бы найти все подходящие слова для каждого регулярного выражения.

Я не хочу сделать это примерно так:

for regexp in regexp_list:
    for word in word_list:
        found_list = re.findall( regexp, word )
        ...do something with found_list...

Учитывая проблемуЯ работаю над тем, мне do необходимо явно зациклить regexp_list, но я бы хотел избежать итерации по гораздо большему word_list. Есть ли какая-то магия регулярных выражений, которая позволит мне сделать это, например:

for regexp in regexp_list:
    found_list = re.findall_in_word_list( regexp, word_list )

Я думал об использовании дерева суффиксов для хранения списка слов и использования специальной версии поиска, которая обрабатывает? 'sd (требующий поиска по дереву суффиксов в глубину), но я бы предпочел использовать уже существующее решение, если оно доступно.

Мое решение проблемы может использовать либо Java8 или Python 3 (или библиотеки NLP на любом языке, если необходимо).

Answer 1

Ваша лучшая ставка может быть:

for regexp in regexp_list:
    for word in word_list:
        found_list = re.findall( regexp, word )
        ...do something with found_list...

и вместо этого:

string_of_list='uniq_delimiter_character_or_sequence'.join(word_list)
for regexp in regexp_list:
    found_list = re.findall( regexp, string_of_list )
        ...do something with found_list...

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

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

Answer 2

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

В Python «внутренняя» команда может иметь большое значение по сравнению с циклом (Python относительно медленный, когда выполняет собственный цикл, но многие подпрограммы кодируются в C / Assembly), но повторение в Java не добавитзначительные накладные расходы (Java почти такой же быстрый, как C для этого типа операций, и довольно легко поточить).

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

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