Open Source Translation Memory System

In Fortsetzung des Teils 2 will ich nun erläutern wie die unscharfe Suche - "Fuzzy Search" implementiert wird.

Ein paar Sätze allgemein zur unscharfen Suche in openTMS. Die unscharfe Suche findet in zwei Schritten (zwei Filter) statt. Zuerst wird in einem sogenannten KD-Tree eine Suche durchgeführt, die als Ergebnis ein Menge von potentiellen passenden Kandiaten liefert. Der KD-Tree wird im folgenden auch als Fuzzy-Baum (Index) bezeichnet.

Der KD-Tree ist eine spezielle Baumstruktur, die das unscharfe Suchen in multidimensionalen Datenstrukturen (Räumen) ermöglicht. In unserem speziellen Anwendungsfall wird ein Segment in Trigramme zerlegt und die Trigramme in einen Index (0..N-1) abgebildet. Bei Segementen der Länge k erhält man damit k-2 Trigramme. Dazu gibt es einen Vektor V der Länge N V[0..[N-1], in dem jedes Vektorelement ein Häufigkeitszähler darstellt. Der errechnete Trigram-Index m erhöht nun das Vektorelement V[m] um den Wert 1. Damit stellt dieser Vektor eine Häufigkeitsverteilung der Trigramme des Segments dar, normiert auf eine bestimmte Vektorlänge. Durch diese Normierung können natürlich auch verschiedene Trigramme auf ein Vektorelement abgebildet werden. Dieser Häufigkeitsvektor wird im KD-Tree gespeichert. Die unscharfe Suche im KD-Tree liefert nun eine Menge passender Kandidaten mit einem bestimmten maximalen Abstand - basierend auf der Trigram-Verteilung.

In dieser Menge von potentiellen passenden (Trigram basierten) Kandiaten werden nun alle Treffer (die Segmente der Ausgangssprache) mit dem zu suchenden Ausgangssegment mit Hilfe der Levenshtein-Ähnlichkeit verglichen und alle Treffer eliminiert, die nicht dem Ähnlichkeitskriterium entsprechen. Als Ähnlichkeitskriterium ist ein Prozentwert definiert, wobei 100% exakte Übereinstimmung bedeutet. Mehr Information zum Verfahren finden sich hier: www.heartsome.de/arayatest/FOLTTreffen16022009.pdf.

Der Fuzzy Baum (Index) wird im Package de.folt.fuzzy implementiert, Levenshtein im Package de.folt.similarity.

Ich will nun die Implementierung an einem einfachen Beispiel zeigen. Einen parallelen Korpus als Datenquelle. Unter einem parallelen Korpus sollen hier einfach zwei Textdateien verstanden werden, die exakt gleiche viele Zeilen (Segmente), durch Zeilenenden getrennt, enthalten. Beispiele dafür sind etwa der Europarl-Korpus sh. http://www.statmt.org/europarl/.

Die Implementierung ist in de.folt.models.datamodel.parallelcorpus.ParallelCorpus enthalten.

Wir definieren wieder:

public class ParallelCorpus extends BasicDataSource

Die Klasse BasicDataSource stellt schon fast alles zur verfügung, was wir für die unscharfe Suche benötigen. Im Prinzip brauchen wir nur noch eine Methode zum Lesen der Daten aus einer Datei und zum Speichern der Änderungen.

Wir brauchen als erstes einen Konstruktor für public ParallelCorpus(DataSourceProperties dataSourceProperties):

    public ParallelCorpus(DataSourceProperties dataSourceProperties)
    {
        

super legt alle Tabellen und auch den Fuzzy Baum an!

        super(dataSourceProperties);
        

Tabelle mit den geladenen Sprachen

        languagesLoaded = new Hashtable();
        String dataSourceName = (String) dataSourceProperties.get("dataSourceName");
        // basically needed just for creating the data source. But not really needed - in case of translation the corlus needs to be loaded anyway.
        String sourceLanguage = (String) dataSourceProperties.get("sourceLanguage");
        String targetLanguage = (String) dataSourceProperties.get("targetLanguage");
        // read the entries and store them
       
       

Prüfung ob die Dateien existieren - Bsp: mycorpus.de und mycorpus.en für de und en

        File fsource = new File(dataSourceName + "." + sourceLanguage);
        if (!fsource.exists())
        {
            this.setLastErrorCode(OpenTMSConstants.OpenTMS_ID_SUCCESS);
            return;
        }
        File ftarget = new File(dataSourceName + "." + targetLanguage);
        if (!ftarget.exists())
        {
            this.setLastErrorCode(OpenTMSConstants.OpenTMS_ID_SUCCESS);
            return;
        }
         

Hier werden die Segmente geladen

        loadParallelCorpusEntries(dataSourceName + "." + sourceLanguage, dataSourceName + "." + targetLanguage);

    }

Nun kommt die wichtigste Funktion - loadParallelCorpusEntries. Sie lädt die Segment aus den beiden Dateien und stellt sie zum Übersetzen zur Verfügung.

Hier eine erste, wichtige Anmerkung. Dieses Implementierungsbeispiel spiecht alle Objekte (MultiLingualObject, MonoLingualObject) im Hauptspeicher. Damit ist eine rasche und effiziente Suche möglich. Andere Implementierungen, z.B. die für db4o greifen für die Objekte auf das zugrunde liegende datenbanksystem zurück und sind damit weniger Hauptspeicher intensiv. Die Fuzzy Methoden unterstützen verschiedene Speicherarten, es wir aber auf jeden Fall empfohlen, einen Typ zu verwenden, der zumindest das Segment und einen Identifkator im Fuzzy-Baum (KD-Tree) abspeichert.

    private int loadParallelCorpusEntries(String sourceFile, String targetFile)
    {
        String sourceLanguage = (String) dataSourceProperties.get("sourceLanguage");
        String targetLanguage = (String) dataSourceProperties.get("targetLanguage");
        String encoding = (String) dataSourceProperties.get("encoding");
        if (encoding == null)
            encoding = "ISO-8859-1";
        int multiID = 0;
        try
        {
            BufferedReader sourceBuffer = new BufferedReader(new InputStreamReader(new FileInputStream(sourceFile), encoding));
            BufferedReader targetBuffer = new BufferedReader(new InputStreamReader(new FileInputStream(targetFile), encoding));
            String sourceLine = "";
            String targetLine = "";

            while (((sourceLine = sourceBuffer.readLine()) != null) && ((targetLine = targetBuffer.readLine()) != null))
            {
                if (sourceLine.equals(""))
                    continue;
                if (targetLine.equals(""))
                    continue;

Erzeugen der MultiLingalen und MonoLingualen Objekte

                MultiLingualObject multi = new MultiLingualObject();
                multi.setId(multiID++);
                MonoLingualObject sourceMono = new MonoLingualObject();
                sourceMono.setLanguage(sourceLanguage);
                sourceMono.setFormattedSegment(sourceLine);
                sourceMono.setPlainTextSegment(sourceLine);

                MonoLingualObject targetMono = new MonoLingualObject();
                targetMono.setLanguage(targetLanguage);
                targetMono.setFormattedSegment(targetLine);
                targetMono.setPlainTextSegment(targetLine);

Prüfen, ob sie schon existieren. Wenn ja, ignorieren - als keine doppelten Einträge.

                Vector sourceresult = this.search(sourceMono, null);
                Vector targetresult = this.search(targetMono, null);
                boolean bFound = false;
                if ((sourceresult != null) && (sourceresult.size() > 0) && (targetresult != null) && (targetresult.size() > 0))
                {
                    for (int i = 0; i < sourceresult.size(); i++)
                    {
                        for (int j = 0; j < sourceresult.size(); j++)
                        {
                            if (sourceresult.get(i).getParentMultiLingualObject() == targetresult.get(j).getParentMultiLingualObject())
                            {
                                bFound = true;
                                break;
                            }
                        }
                        if (bFound)
                            break;
                    }
                    if (bFound)
                        continue;
                }

                multi.addMonoLingualObject(sourceMono);
                multi.addMonoLingualObject(targetMono);

Und nun der wichtigste Aufruf - Speichern der Objekte - hier im Hauptspeicher. In addMultiLingualObject - Methode aus BasicdataSource - werden sowohl die Objekte gespeichert und in den Fuzzy-Baum (Index) gespeichert.

                super.addMultiLingualObject(multi, false);
                multi = null;

            }
            sourceBuffer.close();
            targetBuffer.close();
            languagesLoaded.put(sourceLanguage + ":" + targetLanguage, "true");
        }
        catch (UnsupportedEncodingException e)
        {
            e.printStackTrace();
        }
        catch (FileNotFoundException e)
        {
            e.printStackTrace();
        }
        catch (Exception ex)
        {
            ex.printStackTrace();
        }

        return multiID;

    }

Und nun die Kernfunktion - Speichern der Objekte aus der BasicDataSource.

    public boolean addMultiLingualObject(MultiLingualObject multiLingualObject, boolean mergeObjects)
    {
        

Speichern des MultiLingualObject in einem Cache-Speicher

        this.multiLingualObjectCache.put(multiLingualObject.getId() + "", multiLingualObject);
        Vector monos = multiLingualObject.getMonoLingualObjectsAsVector();
        for (int j = 0; j < monos.size(); j++)
        {
            

Speichern des MonoLingualObject (s) in einem Cache-Speicher

            MonoLingualObject mono = monos.get(j);
            if (langMonoLingualHashtable.containsKey(mono.getLanguage()))
            {
                Hashtable hashMono = langMonoLingualHashtable.get(mono.getLanguage());
                hashMono.put(mono.getUniqueID(), mono);
            }
            else
            {
                Hashtable hashMono = new Hashtable();
                langMonoLingualHashtable.put(mono.getLanguage(), hashMono);
                hashMono.put(mono.getUniqueID(), mono);
            }
            

Speichern des MonoLingualObject (s) in Fuzzy Baum (KD-Tree) - das ist alles!

            if (fuzzyTree != null)
            {
                

Das MonoLingualObject wird in ein MonoLingualFuzzyNode gespeichert

                MonoLingualFuzzyNode fuzzyNodeToAdd = new MonoLingualFuzzyNode(mono);
                

Der MonoLingualFuzzyNode wird iim Fuzzy Baum gespeichert

                fuzzyTree.insertFuzzyNode(fuzzyNodeToAdd);
            }
        }

        bChanged = true;
        return true;
    }

Und hier nun die translate Methode... Auch sie ist sehr einfach zu schreiben.

    public Element translate(Element transUnit, Element file, XliffDocument xliffDocument, String sourceLanguage, String targetLanguage, int matchSimilarity, Hashtable translationParameters)
            throws OpenTMSException
    {
        

Falls wirklich eine andere Sprachkombination eingegeben wurde, wird diese nun geladen...

        if (!languagesLoaded.containsKey(sourceLanguage + ":" + targetLanguage))
        {
            String dataSourceName = (String) dataSourceProperties.get("dataSourceName");
            String sourceFile = dataSourceName + "." + sourceLanguage;
            String targetFile = dataSourceName + "." + targetLanguage;
            loadParallelCorpusEntries(sourceFile, targetFile);
        }
        

Aufruf der Standard translate Methode...

        return super.translate(transUnit, file, xliffDocument, sourceLanguage, targetLanguage, matchSimilarity, translationParameters);
    }

Wir wollen nun aber auch Änderungen in der Data Source speichern. Etwa wenn in einem Editor Änderungen/Löschungen gemacht wurden. Dies erfolgt, bevor die Data Source geschlossen wird in der persist Methode.

    public boolean bPersist()
    {
        String sourceLanguage = (String) dataSourceProperties.get("sourceLanguage");
        String targetLanguage = (String) dataSourceProperties.get("targetLanguage");
        String dataSourceName = (String) dataSourceProperties.get("dataSourceName");
        String encoding = (String) dataSourceProperties.get("encoding");
        if (encoding == null)
            encoding = (String) dataSourceProperties.get("codepage");
        if (encoding == null)
            encoding = "ISO-8859-1";
        String sourceFile = dataSourceName + "." + sourceLanguage;
        String targetFile = dataSourceName + "." + targetLanguage;

        try
        {
            FileOutputStream sourceOut = new FileOutputStream(sourceFile);
            Writer sourceOutWriter = new OutputStreamWriter(sourceOut, encoding);

            FileOutputStream targetOut = new FileOutputStream(targetFile);
            Writer targetOutWriter = new OutputStreamWriter(targetOut, encoding);
						

Wir holen und hier alle Einträge. Dazu dient initEnumeration(), die schon direkt von BasicDataSource unterstützt wird.. Der Rest ist ziemlich einfach, Segmente werden in die Datei geschrieben.

            this.initEnumeration();
            while (this.hasMoreElements())
            {
                MultiLingualObject multi = this.nextElement();
                Vector sourceMonos = multi.getMonoLingualObjectsAsVector(sourceLanguage);
                if (sourceMonos.size() == 0)
                    continue;
                Vector targetMonos = multi.getMonoLingualObjectsAsVector(targetLanguage);
                if (targetMonos.size() == 0)
                    continue;
                sourceOutWriter.write(sourceMonos.get(0).getFormattedSegment() + "\n");
                targetOutWriter.write(targetMonos.get(0).getFormattedSegment() + "\n");
            }
            targetOutWriter.close();
            sourceOutWriter.close();
            targetOut.close();
            sourceOut.close();
        }
        catch (UnsupportedEncodingException e)
        {
            e.printStackTrace();
            return true;
        }
        catch (FileNotFoundException e)
        {
            e.printStackTrace();
            return true;
        }
        catch (Exception ex)
        {
            ex.printStackTrace();
            return true;
        }

        return true;
    }
    
    

Hier die Implementierung initEnumeration() aus der BasicDatSource

    
    public void initEnumeration()
    {
        if (multiLingualObjectCache != null)
            multiEnum = multiLingualObjectCache.elements();
        else
            multiEnum = null;
    }
    

und ...

    public boolean hasMoreElements()
    {
        if (multiEnum != null)
            return multiEnum.hasMoreElements();
        else
            return false;
    }

Im nächsten Beitrag werde ich die unterschiedlichen Fuzzy-Baum (KD Tree) Typen erläutern.

Dr. Klemens Waldhör klemens.waldhoer @ opentms.de - Heartsome Europe GmbH www.heartsome.de