Gale-Church-algoritmus

• IPA:

Gale-Church-algoritmus

1. (matematika)

A Gale-Church-algoritmus egy statikus szövegszegmentáló algoritmus, amelyet bilingual (kétnyelvű) szövegek igazítására terveztek, például mondatok illesztésére egy forrásnyelvi és célnyelvi szöveg között. A módszert William A. Gale és Kenneth W. Church dolgozta ki 1991-ben.

---

• Kétnyelvű szövegek mondatonként történő igazítása.
• A cél: Azonosítani, hogy a forrásnyelvi mondatok mely célnyelvi mondatokkal állnak párban.
• Feltételezés: A mondatok hossza (karakterek vagy szavak száma) statisztikailag korrelál a két nyelv között.

---

1. Hosszúság alapú korreláció:

  * A forrásnyelvi és célnyelvi mondatok hossza (karakterek száma) között lineáris összefüggés van.
  * Ha egy mondat hosszabb a forrásnyelven, akkor általában hosszabb a célnyelven is.

1. Valószínűségi modell:

  * A mondatok hosszának különbségét egy normális eloszlás alapján modellezik:

$${\displaystyle P(l|s,t)\sim \exp \left(-{\frac {(l-\mu )^{2}}{2\sigma ^{2}}}\right)}$$ ahol:

  * \( l \): a forrásnyelvi mondat és a célnyelvi mondat hosszának különbsége,
  * \( \mu \): a várható érték,
  * \( \sigma \): a szórás.

1. Dinamikus programozás:

  * A mondatok illesztéséhez egy dinamikus programozási táblát építünk, ahol a cél a költség minimalizálása.

---

• Input:

  * Forrásnyelvi mondatok listája: ${\displaystyle S=}$
  * Célnyelvi mondatok listája: ${\displaystyle T=}$

• Hosszkülönbség modell:

  * A mondatok hosszának különbségét a fenti valószínűségi modell becsüli.

• Dinamikus programozás:

  * A táblázat kitöltésével keressük meg a lehetséges mondatillesztéseket, amelyek minimalizálják a költséget.

---

1. Inicializálás:

  * Hozz létre egy ${\displaystyle n\times m}$-es dinamikus programozási táblázatot, ahol ${\displaystyle n}$ a forrásnyelvi mondatok száma, ${\displaystyle m}$ a célnyelvi mondatok száma.

1. Költség kiszámítása:

  * A költség a mondatok hosszának különbsége alapján számítandó.

1. Dinamikus programozás:

  * Engedélyezett illesztési típusok:
    * 1-1: Egy forrásnyelvi mondat illeszkedik egy célnyelvi mondathoz.
    * 1-0 vagy 0-1: Egy mondat kimarad (hiányzó pár).
    * 1-2 vagy 2-1: Mondatok összevonhatók vagy szétbonthatók.

1. Visszafejtés:

  * A dinamikus programozási tábla alapján rekonstruáljuk az optimális mondatpárokat.

---

import numpy as np

def gale_church_align(source, target):
    """
    Gale-Church algoritmus egyszerű implementációja.
    """
    n = len(source)
    m = len(target)
    dp = np.zeros((n + 1, m + 1))
    backtrack = np.zeros((n + 1, m + 1), dtype=int)
    
    # Költségfüggvény
    def cost(s_len, t_len):
        diff = abs(s_len - t_len)
        return diff  # Egyszerű költség
    
    # Dinamikus programozás
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            c1 = dp + cost(len(source), len(target))
            c2 = dp + cost(len(source), 0)
            c3 = dp + cost(0, len(target))
            
            dp = min(c1, c2, c3)
            backtrack = np.argmin()
    
    # Visszafejtés
    alignment = 
    i, j = n, m
    while i > 0 and j > 0:
        if backtrack == 0:
            alignment.append((source, target))
            i -= 1
            j -= 1
        elif backtrack == 1:
            alignment.append((source, None))
            i -= 1
        else:
            alignment.append((None, target))
            j -= 1
    
    return alignment

# Példa
source_sentences = 
target_sentences = 

alignment = gale_church_align(source_sentences, target_sentences)

print("Illesztett mondatpárok:")
for s, t in alignment:
    print(f"Source: {s} | Target: {t}")

---

1. Egyszerű és gyors:

  * Hosszúsági korrelációra épít, ami könnyen számítható.

1. Hatékony:

  * A dinamikus programozás segítségével lineáris időben fut.

---

1. Nyelvi szerkezetek eltérései:

  * A nyelvtani eltérések vagy fordítási különbségek esetén pontatlan lehet.

1. Szókincs figyelmen kívül hagyása:

  * Csak a mondatok hosszát vizsgálja.

---

1. Fordítói korpuszok igazítása:

  * Gépi fordításhoz használt kétnyelvű adatok előállítása.

1. Szövegillesztés:

  * Kétnyelvű dokumentumok mondatainak illesztése.

1. Szövegbányászat:

  * Fordítási párhuzamosságok feltérképezése.

A Gale-Church-algoritmus egyszerűsége és hatékonysága miatt széles körben használt nyelvtechnológiai feladatokban.

• Gale-Church-algoritmus - Értelmező szótár (MEK)
• Gale-Church-algoritmus - Etimológiai szótár (UMIL)
• Gale-Church-algoritmus - Szótár.net (hu-hu)
• Gale-Church-algoritmus - DeepL (hu-de)
• Gale-Church-algoritmus - Яндекс (hu-ru)
• Gale-Church-algoritmus - Google (hu-en)
• Gale-Church-algoritmus - Helyesírási szótár (MTA)
• Gale-Church-algoritmus - Wikidata
• Gale-Church-algoritmus - Wikipédia (magyar)