Я недавно написал решение для этого.Мое решение не является надежным, и я не думаю, что оно будет вычислительно жизнеспособным для больших объемов текста, но мне кажется, что оно хорошо работает для небольших предложений.
Предположим, у вас есть две строки текста:
- "LETMEBEGINBYSAYINGTHANKS"
- "UNGHSYINDJFHAKJSNFNDKUAJUD"
Цель состоит в том, чтобы определить, что 1., вероятно, является английским, а 2. - нет.Интуитивно, мой разум определяет это путем поиска границ слов в английских словах в предложениях (LET, ME, BEGIN и т. Д.).Но это не просто в вычислительном отношении, потому что есть перекрывающиеся слова (BE, GIN, BEGIN, SAY, SAYING, THANK, THANKS и т. Д.).
Мой метод выполняет следующие действия:
- Возьмите пересечение
{ known English words } и { all substrings of the text of all lengths }. - Постройте граф вершин, позиции которого являются начальными индексами слов в предложении, с направленными ребрами к начальным позициям буквыпосле конца слова.Например,
(0) будет L, поэтому «LET» может быть представлен (0) -> (3), где (3) равно M, так что это «LET ME». - Найдите наибольшее целое число
n между 0 и len(text), для которого существует простой направленный путь от индекса 0 до индекса n. - Разделите это число
n на длину текста, чтобы получить приблизительное представление о том, какой проценттекст выглядит как последовательные английские слова.
Обратите внимание, что мой код не допускает пробелов между словами, но я полагаю, вы могли бы адаптировать его для учета пробелов довольно легко.Не для того, чтобы мой код работал, вам нужен файл английского словаря.Я получил один из здесь , но вы можете использовать любой такой файл, и я думаю, что таким образом эта техника может быть распространена и на другие языки.
Вот код:
from collections import defaultdict
# This function tests what percent of the string seems to me to be maybe
# English-language
# We use an English words list from here:
# https://github.com/first20hours/google-10000-english
def englishness(maybeplaintext):
maybeplaintext = maybeplaintext.lower()
f = open('words.txt', 'r')
words = f.read()
f.close()
words = words.lower().split("\n")
letters = [c for c in maybeplaintext]
# Now let's iterate over letters and look for some English!
wordGraph = defaultdict(list)
lt = len(maybeplaintext)
for start in range(0, lt):
st = lt - start
if st > 1:
for length in range(2, st):
end = start + length
possibleWord = maybeplaintext[start:end]
if possibleWord in words:
if not start in wordGraph:
wordGraph[start] = []
wordGraph[start].append(end)
# Ok, now we have a big graph of words.
# What is the shortest path from the first letter to the last letter,
# moving exclusively through the English language?
# Does any such path exist?
englishness = 0
values = set([a for sublist in list(wordGraph.values()) for a in sublist])
numberVertices = len(set(wordGraph.keys()).union(values))
for i in range(2, lt):
if isReachable(numberVertices, wordGraph, i):
englishness = i
return englishness/lt
# Here I use my modified version of the technique from:
# https://www.geeksforgeeks.org/
# find-if-there-is-a-path-between-two-vertices-in-a-given-graph/
def isReachable(numberVertices, wordGraph, end):
visited = [0]
queue = [0]
while queue:
n = queue.pop(0)
if n == end or n > end:
return True
for i in wordGraph[n]:
if not i in visited:
queue.append(i)
visited.append(i)
return False
А вот I/O для исходных примеров, которые я привел:
In [5]: englishness('LETMEBEGINBYSAYINGTHANKS')
Out[5]: 0.9583333333333334
In [6]: englishness('UNGHSYINDJFHAKJSNFNDKUAJUD')
Out[6]: 0.07692307692307693
Итак, примерно говоря, я на 96% уверен, что LETMEBEGINBYSAYINGTHANKS является английским, и на 8% уверен, чтоUNGHSYINDJFHAKJSNFNDKUAJUD это английский.Что звучит правдоподобно!
Чтобы распространить это на гораздо более крупные фрагменты текста, я бы предложил отобрать случайные короткие подстроки и проверить их "английскую".Надеюсь, это поможет!