Gale-Church-algoritmus

Magyar

Kiejtés

• IPA: [ ˈɡɒlɛhurɦɒlɡoritmuʃ]

Főnév

Gale-Church-algoritmus

1. (matematika)

Gale-Church-algoritmus

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.

---

Probléma és cél

• 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.

---

Fő ötlet

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:

$$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.

---

Alapfogalmak

• Input:

  * Forrásnyelvi mondatok listája: $S=[s_{1},s_{2},\dots ,s_{n}]$
  * Célnyelvi mondatok listája: $T=[t_{1},t_{2},\dots ,t_{m}]$

• 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.

---

Algoritmus lépései

1. Inicializálás:

  * Hozz létre egy $n\times m$-es dinamikus programozási táblázatot, ahol $n$ a forrásnyelvi mondatok száma, $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.

---

Python Implementáció

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[i - 1, j - 1] + cost(len(source[i - 1]), len(target[j - 1]))
            c2 = dp[i - 1, j] + cost(len(source[i - 1]), 0)
            c3 = dp[i, j - 1] + cost(0, len(target[j - 1]))
            
            dp[i, j] = min(c1, c2, c3)
            backtrack[i, j] = np.argmin([c1, c2, c3])
    
    # Visszafejtés
    alignment = []
    i, j = n, m
    while i > 0 and j > 0:
        if backtrack[i, j] == 0:
            alignment.append((source[i - 1], target[j - 1]))
            i -= 1
            j -= 1
        elif backtrack[i, j] == 1:
            alignment.append((source[i - 1], None))
            i -= 1
        else:
            alignment.append((None, target[j - 1]))
            j -= 1
    
    return alignment[::-1]

# Példa
source_sentences = ["This is a test.", "It works well.", "Another sentence."]
target_sentences = ["Ceci est un test.", "Ça marche bien.", "Une autre phrase."]

alignment = gale_church_align(source_sentences, target_sentences)

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

---

Előnyök

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.

---

Hátrányok

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.

---

Alkalmazások

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.

Fordítások

Tartalom

angol: Gale–Church algorithm (en)

További információk

• 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)