Corrector ortográfico eficiente: combinación de técnicas de corrección Trie, Edit Distance y Threshold-Based

La revisión ortográfica es esencial para mantener la calidad del contenido escrito y se vuelve aún más crucial para los idiomas con juegos de caracteres y reglas complejos.

Uno de esos idiomas es el tailandés, que tiene una escritura y una gramática únicas. Este artículo discutirá un sistema de corrector ortográfico para el idioma tailandés, explicará el algoritmo involucrado y proporcionará un código de muestra para que pueda comenzar.

El sistema de revisión ortográfica para el idioma tailandés se basa principalmente en tres técnicas: la estructura de datos trie para el almacenamiento y recuperación eficiente de palabras, la distancia de Levenshtein (distancia de edición) para encontrar la palabra coincidente más cercana y un algoritmo de corrección basado en el umbral.
Exploremos cada una de estas técnicas.

1. Estructura de datos Trie

Un trie es una estructura de datos eficiente que se utiliza para almacenar un conjunto dinámico de cadenas. Permite operaciones rápidas de inserción y búsqueda, lo que lo convierte en una opción ideal para el almacenamiento de diccionarios en un corrector ortográfico.

Text Generation in Customer Service (Part 2)

class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_word = True

Puedes pensar en un Trie como un árbol especial con letras conectadas en capas. Por ejemplo, las palabras «murciélago», «batman» y «baño» se almacenarían en un Trie como este:

      (root)
/ 
b
/ 
a
/ 
t   s
/    
man  h   th

2. Distancia de Levenshtein (Editar distancia)

Distancia de Levenshtein (Editar distancia) La distancia de Levenshtein es una medida de la similitud entre dos cadenas. calcula el número mínimo de ediciones de un solo carácter (inserciones, eliminaciones o sustituciones) necesarios para transformar una cadena en otra. Esta métrica es útil para encontrar la palabra coincidente más cercana en el diccionario cuando se detecta un error tipográfico.

La distancia de Levenshtein se puede calcular entre dos cadenas mediante programación dinámica:

def levenshtein_distance(s1, s2):
# Initialize a matrix of zeros with size (len(s1) + 1) x (len(s2) + 1)
distances = [[0 for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]
# Populate the first row and column of the matrix with the appropriate values
for i in range(1, len(s1) + 1):
distances[i][0] = i
for j in range(1, len(s2) + 1):
distances[0][j] = j
# Iterate over the remaining cells of the matrix
for j in range(1, len(s2) + 1):
for i in range(1, len(s1) + 1):
# If the characters at the current positions are equal, the cost is zero
if s1[i-1] == s2[j-1]:
cost = 0
# Otherwise, the cost is 1
else:
cost = 1
# Calculate the minimum cost of the three adjacent cells and add the cost of the current cell
distances[i][j] = min(distances[i-1][j] + 1,      # deletion
distances[i][j-1] + 1,      # insertion
distances[i-1][j-1] + cost)  # substitution
# The Levenshtein distance is the value in the bottom right corner of the matrix
return distances[-1][-1]
También te puede interesarNuevas ideas en torno a los códigos LDPC parte 1 (Telecomunicaciones)

Esta imagen de ejemplo de funcionamiento:

d = deletion, s = substitution, i = insertion

distances = d=1 s=2 s=2 i=1 s=2 
= 8 

Aquí hay un ejemplo de cómo se puede usar esta función para encontrar la distancia entre dos cadenas:

s1 = "เราไม่รักภาษาไทย"
s2 = "เรารักภาษาไทย"
distance = levenshtein_distance(s1, s2)
print(f"The Levenshtein distance between '{s1}' and '{s2}' is {distance}")
También te puede interesarUsando Haystack para crear un motor de búsqueda neuronal para la ley holandesa, parte 4: probando diferentes vectores …

Producción:

The Levenshtein distance between 'เราไม่รักภาษาไทย' and 'เรารักภาษาไทย' is 2

Esto significa que se necesitan dos ediciones de un solo carácter (una eliminación de ‘no’ y una sustitución de ‘me encanta’ por ‘no me encanta’) para transformar «No amamos el tailandés» en «Nos encanta el tailandés».

3. Algoritmo de corrección basado en umbral

Algoritmo de corrección basado en umbrales El algoritmo de corrección basado en umbrales compara cada palabra del texto de entrada con el diccionario. Si la palabra no se encuentra en el diccionario, el algoritmo busca la palabra coincidente más cercana en el diccionario, según la distancia de edición, y corrige la palabra si la distancia está por debajo de un umbral predefinido.

Aquí está el fragmento de código proporcionado:

for word in sentence:
if word not in mydict: 
best_candidate = None
for candidate in mydict: 
if dist(word, candidate) < dist(word, best_candidate) and dist(word, candidate) < threshold:
best_candidate = candidate
word = best_candidate

Explicación del fragmento de código:

Ahora que tenemos una comprensión básica del algoritmo, implementemos un sistema de revisión ortográfica para el idioma tailandés usando Python. Para esta implementación, utilizaremos el pythainlp biblioteca, que proporciona herramientas de procesamiento del idioma tailandés.

Primero, instale el pythainlp biblioteca usando pip:

pip install pythainlp

Ahora, implementemos el corrector ortográfico:

from pythainlp import thai_words
from pythainlp.util import trie
from pythainlp.util import normalize
from pythainlp.tokenize import syllable_tokenize
from pythainlp.spell import NorvigSpellChecker
def build_dictionary():
words = set(thai_words())
return trie.dict_trie(words)
def dist(word1, word2):
# Implement your preferred distance function here, such as Levenshtein distance.
# For simplicity, we will use the NorvigSpellChecker's distance function.
spell_checker = NorvigSpellChecker(custom_dict=set())
return spell_checker._edit_distance(word1, word2)
def correct_word(word, dictionary, threshold):
if word not in dictionary:
best_candidate = None
best_distance = float('inf')
for candidate in dictionary:
current_distance = dist(word, candidate)
if current_distance < best_distance and current_distance < threshold:
best_candidate = candidate
best_distance = current_distance
return best_candidate if best_candidate else word
return word
def main():
input_text = "เรารักภาษาไทย"  # Replace with the text you want to check
normalized_text = normalize(input_text)
syllables = syllable_tokenize(normalized_text)
dictionary = build_dictionary()
threshold = 3  # Set an appropriate threshold value for the correction algorithm
corrected_syllables = [correct_word(syllable, dictionary, threshold) for syllable in syllables]
corrected_text = ''.join(corrected_syllables)
print("Original text:", input_text)
print("Corrected text:", corrected_text)
if __name__ == "__main__":
main()

La entrada a este programa es una cadena de texto tailandés y la salida es el mismo texto con la ortografía corregida. Aquí hay algunos ejemplos de entradas y salidas esperadas:

Ejemplo 1:

Input: “เราไม่รักภาษาไทย”
Output: “เราไม่รักภาษาไทย” (The input text is already correctly spelled, so the output is the same as the input.)

Ejemplo 2:

Input: “เเมวน่ารักมาก” 
Output: “แมวน่ารักมาก” (The initial “เ” character is a tone marker, not part of the syllable, so it is removed by the normalization step.)

Ejemplo 3:

Input: “สวัสดีค่าาา” 
Output: "สวัสดีค่ะ" (The "า" character after the "ค่า" should be "ะ".)

Ejemplo 4:

Input: “กาแฟๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆ”
Output: "กาแฟ" (The input text contains many repeated characters, which are not valid Thai syllables. The output text contains only the corrected syllables.)

Ejemplo 5:

Input: “ตัวเลขไม่มีเสียงทำไม” 
Output: "ตัวเลขไม่มีเสียงทำไม" (The input text contains only numbers and no Thai syllables, so it is already correctly spelled.)

En este código, primero construimos un diccionario basado en trie usando el pythainlp biblioteca. Luego, tokenizamos el texto de entrada en sílabas y usamos el correct_word Función para corregir cada sílaba según el diccionario y el umbral. Finalmente, unimos las sílabas corregidas para formar el texto corregido.

Conclusión

Implementar un sistema de revisión ortográfica para el idioma tailandés es una tarea desafiante pero gratificante. Mediante el uso de estructuras de datos de prueba, algoritmos de distancia de edición y un algoritmo de corrección basado en umbrales, podemos buscar y corregir de manera eficiente las palabras mal escritas. El código de muestra provisto demuestra una implementación simple usando el pythainlp biblioteca, que se puede mejorar aún más y adaptar a casos de uso específicos.