Решение, представленное ниже, имеет приблизительно O (n) сложность, когда дело доходит до времени выполнения, где n - количество токенов в каждом предложении.
Для 5 миллионов предложений и вашего concepts.txt он выполняет требуемые операции за ~ 30 секунд, см. Базовый тест в третьем разделе.
Когда речь идет о сложности пространства, вам придется сохранить вложенную словарную структуру (давайте пока упростим ее), скажем, это O (c * u) , где u уникально токены для определенной длины понятия (по токену), в то время как c - длина понятия.
Трудно точно определить точные сложности, но это очень похоже на это (для данных вашего примера итот, который вы предоставили [concepts.txt] , они довольно точные, но мы подробно расскажем о процессе реализации).
Я полагаю, вы можете разбить свои концепции и предложения на пробелы,Если это не так, я бы посоветовал вам взглянуть на spaCy , который предоставляет более интеллектуальный способ токенизации ваших данных.
1.Введение
Давайте рассмотрим ваш пример:
concepts = [
["natural language processing", "text mining", "texts", "nlp"],
["advanced data mining", "data mining", "data"],
["discourse analysis", "learning analytics", "mooc"],
]
Как вы сказали, каждый элемент из концептов должен быть сопоставлен с первым, поэтому в Pythonish он будет идти примерно так:
for concept in concepts:
concept[1:] = concept[0]
Задача была бы легкой, если бы все концепции имели длину токена, равную единице (что здесь не так), и были бы уникальными.Давайте сосредоточимся на втором случае и одном конкретном (немного измененном) примере concept, чтобы увидеть мою точку зрения:
["advanced data mining", "data something", "data"]
Здесь data будет отображаться на advanced data mining, НО data something, который состоит из data, должен отображаться перед ним.Если я вас правильно понимаю, вы бы хотели, чтобы это предложение:
"Here is data something and another data"
было отображено на:
"Here is advanced data mapping and another advanced data mining"
Вместо наивного подхода:
"Here is advanced data mapping something and another advanced data mining"
Обратите внимание, что для второго примера мы отобразили только data, а не data something.
Чтобы расставить приоритеты data something (и другие, соответствующие этому шаблону), я использовал структуру массива, заполненную словарямигде более ранние концепции в массиве - это те, которые имеют более длинный токен.
Для продолжения нашего примера такой массив будет выглядеть так:
structure = [
{"data": {"something": "advanced data mining"}},
{"data": "advanced data mining"},
]
Обратите внимание, что если мы пойдемчерез токены в этом порядке (например, сначала пройдя первый словарь с последовательными токенами, если совпадений не было найдено, перейдите ко второму словарю и т. д.), мы сначала получим самые длинные понятия.
2.Код
Хорошо, я надеюсь, что вы поняли основную идею (если нет, опубликуйте комментарий ниже, и я попытаюсь объяснить неясные детали более подробно).
Отказ от ответственности: IЯ не особенно горжусь этим кодом, но он выполняет свою работу и, возможно, еще хуже, я полагаю .
2.1 Иерархический словарь
Во-первых, давайте получим самую длинную концепциюпо токену (исключая первый элемент, так как он является нашей целью, и нам не нужно его когда-либо менять):
def get_longest(concepts: List[List[str]]):
return max(len(text.split()) for concept in concepts for text in concept[1:])
Используя эту информацию, мы можем инициализировать нашу структуру, создавая столько словарей разной длиныконцепций (в приведенном выше примере это будет 2, так что это будет для всех ваших данных. Тем не менее, концепции любой длины подойдут):
def init_hierarchical_dictionaries(longest: int):
return [(length, {}) for length in reversed(range(longest))]
Обратите внимание, я добавляю длину каждой концепциик массиву , IMO проще, когда дело доходит до обхода, вы можете обойтись без него, хотя после некоторых изменений в реализации.
Теперь, когда у нас есть эти вспомогательные функцииКроме того, мы можем создать структуру из списка понятий:
def create_hierarchical_dictionaries(concepts: List[List[str]]):
# Initialization
longest = get_longest(concepts)
hierarchical_dictionaries = init_hierarchical_dictionaries(longest)
for concept in concepts:
for text in concept[1:]:
tokens = text.split()
# Initialize dictionary; get the one with corresponding length.
# The longer, the earlier it is in the hierarchy
current_dictionary = hierarchical_dictionaries[longest - len(tokens)][1]
# All of the tokens except the last one are another dictionary mapping to
# the next token in concept.
for token in tokens[:-1]:
current_dictionary[token] = {}
current_dictionary = current_dictionary[token]
# Last token is mapped to the first concept
current_dictionary[tokens[-1]] = concept[0].split()
return hierarchical_dictionaries
Эта функция создаст наш иерархический словарь, см. комментарии в исходном коде для некоторых пояснений.Возможно, вы захотите создать собственный класс, сохраняющий эту вещь, поэтому его проще использовать.
Это точно такой же объект, как описано в 1.Введение
2.2 Обход словарей
Эта часть намного сложнее, но давайте на этот раз воспользуемся подходом сверху вниз.Начнем легко:
def embed_sentences(sentences: List[str], hierarchical_dictionaries):
return (traverse(sentence, hierarchical_dictionaries) for sentence in sentences)
При наличии иерархических словарей создается генератор, который преобразует каждое предложение в соответствии с отображением понятий.
Сейчас traverse функция:
def traverse(sentence: str, hierarchical_dictionaries):
# Get all tokens in the sentence
tokens = sentence.split()
output_sentence = []
# Initialize index to the first token
index = 0
# Until any tokens left to check for concepts
while index < len(tokens):
# Iterate over hierarchical dictionaries (elements of the array)
for hierarchical_dictionary_tuple in hierarchical_dictionaries:
# New index is returned based on match and token-wise length of concept
index, concept = traverse_through_dictionary(
index, tokens, hierarchical_dictionary_tuple
)
# Concept was found in current hierarchical_dictionary_tuple, let's add it
# to output
if concept is not None:
output_sentence.extend(concept)
# No need to check other hierarchical dictionaries for matching concept
break
# Token (and it's next tokens) do not match with any concept, return original
else:
output_sentence.append(tokens[index])
# Increment index in order to move to the next token
index += 1
# Join list of tokens into a sentence
return " ".join(output_sentence)
Еще раз, если вы не уверены, что происходит, оставьте комментарий .
Используя этот подход, пессимистично, мы выполним O (n * c!) проверок, где n - количество токенов в предложении, c - длина токена самого длинного понятия и его факториал.Этот случай крайне маловероятен на практике, каждый токен в предложении должен почти идеально соответствовать самому длинному понятию плюс все более короткие понятия должны быть префиксами самого короткого (как super data mining, super data и data).
Было бы намного ближе к O (n) для любой практической проблемы, как я уже говорил, используяданные, предоставленные вами в файле .txt, имеют O (3 * n) наихудший случай, обычно O (2 * n).
Обход по каждому словарю :
def traverse_through_dictionary(index, tokens, hierarchical_dictionary_tuple):
# Get the level of nested dictionaries and initial dictionary
length, current_dictionary = hierarchical_dictionary_tuple
# inner_index will loop through tokens until match or no match was found
inner_index = index
for _ in range(length):
# Get next nested dictionary and move inner_index to the next token
current_dictionary = current_dictionary.get(tokens[inner_index])
inner_index += 1
# If no match was found in any level of dictionary
# Return current index in sentence and None representing lack of concept.
if current_dictionary is None or inner_index >= len(tokens):
return index, None
# If everything went fine through all nested dictionaries, check whether
# last token corresponds to concept
concept = current_dictionary.get(tokens[inner_index])
if concept is None:
return index, None
# If so, return inner_index (we have moved length tokens, so we have to update it)
return inner_index, concept
Это составляет "мясо" моего решения.
3.Результаты
Теперь, для краткости, весь исходный код приведен ниже (concepts.txt - это предоставленный вами):
import ast
import time
from typing import List
def get_longest(concepts: List[List[str]]):
return max(len(text.split()) for concept in concepts for text in concept[1:])
def init_hierarchical_dictionaries(longest: int):
return [(length, {}) for length in reversed(range(longest))]
def create_hierarchical_dictionaries(concepts: List[List[str]]):
# Initialization
longest = get_longest(concepts)
hierarchical_dictionaries = init_hierarchical_dictionaries(longest)
for concept in concepts:
for text in concept[1:]:
tokens = text.split()
# Initialize dictionary; get the one with corresponding length.
# The longer, the earlier it is in the hierarchy
current_dictionary = hierarchical_dictionaries[longest - len(tokens)][1]
# All of the tokens except the last one are another dictionary mapping to
# the next token in concept.
for token in tokens[:-1]:
current_dictionary[token] = {}
current_dictionary = current_dictionary[token]
# Last token is mapped to the first concept
current_dictionary[tokens[-1]] = concept[0].split()
return hierarchical_dictionaries
def traverse_through_dictionary(index, tokens, hierarchical_dictionary_tuple):
# Get the level of nested dictionaries and initial dictionary
length, current_dictionary = hierarchical_dictionary_tuple
# inner_index will loop through tokens until match or no match was found
inner_index = index
for _ in range(length):
# Get next nested dictionary and move inner_index to the next token
current_dictionary = current_dictionary.get(tokens[inner_index])
inner_index += 1
# If no match was found in any level of dictionary
# Return current index in sentence and None representing lack of concept.
if current_dictionary is None or inner_index >= len(tokens):
return index, None
# If everything went fine through all nested dictionaries, check whether
# last token corresponds to concept
concept = current_dictionary.get(tokens[inner_index])
if concept is None:
return index, None
# If so, return inner_index (we have moved length tokens, so we have to update it)
return inner_index, concept
def traverse(sentence: str, hierarchical_dictionaries):
# Get all tokens in the sentence
tokens = sentence.split()
output_sentence = []
# Initialize index to the first token
index = 0
# Until any tokens left to check for concepts
while index < len(tokens):
# Iterate over hierarchical dictionaries (elements of the array)
for hierarchical_dictionary_tuple in hierarchical_dictionaries:
# New index is returned based on match and token-wise length of concept
index, concept = traverse_through_dictionary(
index, tokens, hierarchical_dictionary_tuple
)
# Concept was found in current hierarchical_dictionary_tuple, let's add it
# to output
if concept is not None:
output_sentence.extend(concept)
# No need to check other hierarchical dictionaries for matching concept
break
# Token (and it's next tokens) do not match with any concept, return original
else:
output_sentence.append(tokens[index])
# Increment index in order to move to the next token
index += 1
# Join list of tokens into a sentence
return " ".join(output_sentence)
def embed_sentences(sentences: List[str], hierarchical_dictionaries):
return (traverse(sentence, hierarchical_dictionaries) for sentence in sentences)
def sanity_check():
concepts = [
["natural language processing", "text mining", "texts", "nlp"],
["advanced data mining", "data mining", "data"],
["discourse analysis", "learning analytics", "mooc"],
]
sentences = [
"data mining and text mining",
"nlp is mainly used by discourse analysis community",
"data mining in python is fun",
"mooc data analysis involves texts",
"data and data mining are both very interesting",
]
targets = [
"advanced data mining and natural language processing",
"natural language processing is mainly used by discourse analysis community",
"advanced data mining in python is fun",
"discourse analysis advanced data mining analysis involves natural language processing",
"advanced data mining and advanced data mining are both very interesting",
]
hierarchical_dictionaries = create_hierarchical_dictionaries(concepts)
results = list(embed_sentences(sentences, hierarchical_dictionaries))
if results == targets:
print("Correct results")
else:
print("Incorrect results")
def speed_check():
with open("./concepts.txt") as f:
concepts = ast.literal_eval(f.read())
initial_sentences = [
"data mining and text mining",
"nlp is mainly used by discourse analysis community",
"data mining in python is fun",
"mooc data analysis involves texts",
"data and data mining are both very interesting",
]
sentences = initial_sentences.copy()
for i in range(1_000_000):
sentences += initial_sentences
start = time.time()
hierarchical_dictionaries = create_hierarchical_dictionaries(concepts)
middle = time.time()
letters = []
for result in embed_sentences(sentences, hierarchical_dictionaries):
letters.append(result[0].capitalize())
end = time.time()
print(f"Time for hierarchical creation {(middle-start) * 1000.0} ms")
print(f"Time for embedding {(end-middle) * 1000.0} ms")
print(f"Overall time elapsed {(end-start) * 1000.0} ms")
def main():
sanity_check()
speed_check()
if __name__ == "__main__":
main()
Результаты проверки скорости представлены ниже:
Time for hierarchical creation 107.71822929382324 ms
Time for embedding 30460.427284240723 ms
Overall time elapsed 30568.145513534546 ms
Итак, для 5 миллионов предложений (5 предложений, которые вы предоставили сцепленными 1 миллион раз) и предоставленного вами файла концепций (1,1 МБ), для отображения концепта требуется примерно 30 секунд, что, я полагаю, неплохо..
В худшем случае словарь должен занимать столько же памяти, сколько ваш входной файл (в данном случае concepts.txt), но обычно он будет ниже / намного ниже, так как это зависит от комбинации длины концептов иуникальные слова для этих слов.