Tokenização de texto não espaçado em palavras usando algoritmos eficientes

No domínio do processamento de linguagem natural, a capacidade de dividir um fluxo contínuo de caracteres em palavras significativas é crucial. Este processo, conhecido como tokenização, é particularmente desafiador quando se lida com texto que não possui espaços ou delimitadores.

Declaração de desafio

A tarefa em questão envolve dividir uma string de entrada como "tableapplechairtablecupboard..." em uma lista de palavras, levando em consideração a possibilidade de substrings ambíguas onde uma sequência pode formar múltiplas palavras (por exemplo, "armário" pode ser "copo" ou "board").

Algoritmo: explorando a frequência das palavras

Uma abordagem ingênua de identificar iterativamente a palavra mais longa possível em cada posição produz resultados insatisfatórios em cenários do mundo real. Para superar essa limitação, utilizamos um algoritmo que incorpora a distribuição de frequência de palavras.

Modelagem de frequência de palavras

Presumimos que as frequências de palavras seguem a lei de Zipf, que afirma que a probabilidade de encontrar a n-ésima palavra frequente é aproximadamente 1/(n * log(N)), onde N é o número total de palavras no idioma. Usando um dicionário de custos pré-computado que codifica esse relacionamento, podemos atribuir um custo a cada palavra candidata em potencial.

Abordagem de programação dinâmica

Para determinar a segmentação ideal de palavras, nós empregar programação dinâmica. Iteramos pela string de entrada, mantendo um valor de custo operacional para cada ponto de divisão potencial. Em cada posição, avaliamos as palavras candidatas começando no final da string e selecionamos a divisão com o menor custo.

Implementação de algoritmo

O código Python fornecido oferece uma implementação concisa deste algoritmo:

from math import log

# Precomputed word cost dictionary using Zipf's law
wordcost = ...

# Helper function to find the best word match based on cost
def best_match(i):
    ...

# Function to infer spaces in the input string using dynamic programming
def infer_spaces(s):
    ...

Exemplo de uso

Para utilizar este código, basta inserir a string de texto contínua como segue:

s = 'thumbgreenappleactiveassignmentweeklymetaphor'
print(infer_spaces(s))

Resultados e avaliação

Este algoritmo demonstra desempenho excepcional mesmo com um dicionário de palavras limitado. Ele tokeniza com sucesso textos complexos com alta precisão.