Seite 1 von 1

Sukhotin Algorithmus zur Erkennung von Vokalen

Verfasst: Freitag 18. November 2022, 16:09
von bi3mw
Hallo,
ich stehe vor der ( selbst gestellten ) Aufgabe den Sukhotin`schen Algorithmus in Python umzusetzen. Dabei habe ich ich mich vermutlich gedanklich "verrannt", soll heißen der Einstieg zur Lösung mit einer Liste hat in eine Sackgasse geführt.
Aber zuerst einmal die Problembeschreibung. Ich verlinke hier mal den Text von Jacques Guy. Nicht das ich zu bequem wäre selbst das Problem zu beschreiben aber kleinschrittiger würde ich es auch nicht hinbekommen.

http://languagelog.ldc.upenn.edu/myl/guySukhotin.pdf

Meine konkrete Frage zu dem Problem: Ist der Versuch die Matrix mit einer zweidimensionalen Liste "nachzubilden" der richtige Ansatz oder muss zur Lösung ganz anders vorgegangen werden ? Mir ist leider nicht klar wie ich die benachbarten Buchstaben innerhalb der Liste vergleichen und die Füllwerte (1,2,3,4) enstprechend ändern kann. Zumal die Größe der "matrix" ja auch, je nach Wortlänge, variieren kann.

Hier der ( eigentlich nutzlose ) Code, nur um zu zeigen wie ich einsteigen wollte:

Code: Alles auswählen

#!/usr/bin/env python
# -*-coding: utf-8-*

import numpy as np

eingabe = ("SAGIT") # das wird später input
liste = list(("SAGIT"))
laenge = (len(liste))
new_list = []
n = 1

for start_index in range(0, len(liste), n):
    counter = n + 1
    new_list.extend(liste[start_index:start_index+n])
    for counter in range(laenge): 
        new_list.append(counter)
        new_list.append(0)
        new_list.pop()        
        length = len(new_list)
        split_index = (length // (laenge + 1))
splits = np.array_split(new_list, split_index)

print("Block:")
print(liste)
for array in splits:
    # liste2 = array.tolist()
    print(list(array))

Re: Sukhotin Algorithmus zur Erkennung von Vokalen

Verfasst: Freitag 18. November 2022, 16:58
von __blackjack__
@bi3mw: Ich würde ja empfehlen erst mal keine komplexeren Sachen zu machen, sondern die Grundlagen zu lernen. Dazu gehört neben keinen offensichtlich komplett unsinnigen Code zu schreiben, auch passende Namen zu überlegen die dem Leser verraten, was die Werte dahinter im Programm bedeuten.

Re: Sukhotin Algorithmus zur Erkennung von Vokalen

Verfasst: Freitag 18. November 2022, 19:01
von nezzcarth
Die Darstellung als Matrix ist gut, um den Algorithmus zu erklären, aber so würde ich es nicht implementieren. Generell würde ich das nicht "mechanisch" runter programmieren, wie es im Text beschrieben wird. Wenn man, wie __blackjack__ schon meinte, mit den Kernfeatures von Python vertraut ist, gibt es ggf. andere Wege, wie man das sinnvoll umsetzen könnte. Der Algorithmus geht außerdem davon aus, dass man weder die Leserichtung noch den Anfang kennt. Wenn man das aber doch tut (z.B. um "Vokale" in einem deutschsprachigen Text zu finden) sind weitere Vereinfachungen möglich. Im Prinzip muss man eigentlich nur Bigramm-Häufigkeiten betrachten und vergleichen.

Re: Sukhotin Algorithmus zur Erkennung von Vokalen

Verfasst: Freitag 18. November 2022, 19:22
von bi3mw
@nezzcarth: Danke für Deinen konstruktiven Kommentar. Allerdings möchte ich den Algorithmus auf die Transkription einer unbekannten Sprache anwenden (sog. "Voynich Manuskript"). Eine Vereinfachung kommt hier darum nur bedingt in Frage.

Re: Sukhotin Algorithmus zur Erkennung von Vokalen

Verfasst: Samstag 19. November 2022, 20:08
von nezzcarth
Das Voynich-Manuskript ist mir bekannt. Nachfolgend mal eine naive Implementation des Algorithmus', die noch relativ nah am Aufsatz dran ist und mit Dictionaries und Sets arbeitet:

Code: Alles auswählen

#!/usr/bin/env python
from collections import defaultdict
from operator import itemgetter


def classify_chars(text):
    vowels = set()
    consonants = set()
    if text:
        text = f"{text}{text[0]}"
        matrix = defaultdict(int)
        row_sums = defaultdict(int)
        for first, second in zip(text, text[1:]):
            consonants.add(first)
            if first != second:
                matrix[first, second] += 1
                matrix[second, first] += 1
                row_sums[first] += 1
                row_sums[second] += 1
        while any(row_sum > 0 for row_sum in row_sums.values()):
            vowel = max(row_sums.items(), key=itemgetter(1))[0]
            vowels.add(vowel)
            consonants -= vowels
            for consonant in consonants:
                frequency = matrix.get((consonant, vowel), 0)
                row_sums[consonant] -= 2 * frequency
            row_sums = {key: value for key, value in row_sums.items() if key not in vowels}
    return vowels, consonants


def main():
    text = "SAGITTA"
    vowels, consonants = classify_chars(text)
    print("Vowels:", ", ".join(sorted(vowels)))
    print("Consonants:", ", ".join(sorted(consonants)))


if __name__ == "__main__":
    main()

Übrigens hat der Algorithmus deutliche Schwächen, wie man schnell merkt, wenn man den mal auf größere Textmengen anwendet. Zur Übung natürlich nett, aber für den ernsthaften Einsatz sollte man eines der moderneren Verfahren in Betracht ziehen.

Re: Sukhotin Algorithmus zur Erkennung von Vokalen

Verfasst: Samstag 19. November 2022, 21:28
von bi3mw
@nezzcarth: Danke für Deine Unterstützung ! Ich werde mir den Code mal in Ruhe ansehen um möglichst den Programmablauf zu verstehen. Bei meinen Spielereien mit Numpy - Arrays habe ich auch schon etwas gelernt, aber das war ja am Ende nicht zielführend.

Mit Deiner Erlaubnis würde ich den Code gerne im Voynich - Forum vorstellen ( natürlich mit Nennung Deiner Authorenschaft ). Ich könnte mir vorstellen das dort auch Interesse daran besteht. Brauchbare Tools sind immer Mangelware ;)

P.S: kann man den Thread irgendwo als gelöst markieren ?

Re: Sukhotin Algorithmus zur Erkennung von Vokalen

Verfasst: Samstag 19. November 2022, 22:03
von nezzcarth
An sich kein Problem. Ich kann aber weder garantieren, dass das korrekt, noch besonders elegant umgesetzt ist. Das war nur als Beispiel/Ansatz zur Veranschaulichung gedacht. Evtl. bekommt es hier noch jemand anders besser hin.:)