Stromové řazení (TreeSort)17.5.2025

Zde se jedná již o stěží představitelné struktury (byť zpočátku to může připadat jako brnkačka) a může být problém nejen s chápáním příkladovaných struktur a modelováním si jak to funguje, ale i s představením kde by se mohly použít v praxi. Je asi nepravděpodobné že tomu porozumí někdo bez alespoň základních zkušeností s programováním, stejně tak že by to mělo využití někde jinde než v programování.

Od začátku je problém s tím, že papír či normální monitor zobrazuje ve 2D a nebudu-li připomínat že člověk též nemá jakési 3D vnímání, zůstává stále jen 2D plocha a různé pokusy na ní namodelovat vícerozměrné struktury, kteréž zůstávají modely a netvrdil bych, že podle těch obrázků to někde tak funguje :-).

Klasické pole vs. pole polí

Stromové řazení využívá strukturu zvanou pole polí, která narozdíl od klasického pole nemá všechny buňky, takže se dá připodobnit třeba k větvi stromu než k tabulce.

Nalezení hodnoty na nějakých pozici probíhá stejně, v 2D verzi třeba v pořadí sloupec, řádek a tedy např. klasické pole a A3 dá výsledek 2. U pole polí kde je kmen i všechny větve z jednoho mustru už to lze modelovat třeba jen s písmeny a poté v AC je číslo 2. Narozdíl od 2D pole však pole polí nemá všechny buňky a když třeba C2 vrací 3, tak CB vrátí tak akorát chybu, že položka neexistuje. Oproti klasickému poli však pole polí zabírá méně paměti.

Není možné nějak přehledně kreslit na 2D papír vícerozměrné struktury, ale je možné kreslit vícerozměrné pole polí v hadím stylu jako ve staré hře kde počítačový had rostl z chycených čtverečků.

TreeSort

Základem pro strom je větev která se skládá pouze z použitých znaků. Jaké znaky jsou ve vstupních datech se dá zjistit ArraySortem a to tak, že se budou brát Ascii kódy znaků což jsou čísla.

Pro ukázku třeba slabiky AB, AC a EB. Použitá písmena jsou A, B, C, E a ta se převedou do větve což je pole které má nultý index vyhrazený pro číslo jež bude uvádět počet slova ve stromě.

Ve stromu se to může připodobňovat třeba takto: je celkový počet zaznamenaných slov, a jsou počty konkrétních slov → např. AB je 1×, ale samotné A je 0×.

To v jakém pořadí se Ascii kódy nalinkují do větve je kritérium pro řazení. Ukázka pro více písmen kdy větev bude seřazená dle abecedy:

Nebo kdy diakritická písmena budou třeba až za nediakritickými:

Ukázka jak může být příkladován strom třeba pro slova: BABA, BA, OBA, BAOBAB, OB, BOB, BOA. Nejprve větev z použitých znaků:

Slovo BABA:

BA

OBA

BAOBAB

OB

Předposlední BOB:

A poslední BOA:

Systematické přečtení stromu poté dá výsledek → seřazená slova s počtem kolikrát se vyskytují, unikáty jsou pouze jednou, bez duplicit je výpis bez počtů.

Příklad v Pythonu je bez rekurze, neb s ní to bylo cca o 20% pomalejší.

Komentáře jsou v angličtině, nechtělo se mi je již překládat do češtiny. Na ukázku to stačí a pokud někdo chce algoritmy použít pro nějaký svůj větší projekt, jistě pro něj bude lepší když začne od začátku podle sebe. Ostatně platí to co u předchozích algoritmů, vyplatí se nad tím popřemýšlet a zrealizovat nějakou co nejoptimálnější variantu pro daný projekt.

# run function main()

import time, random

# !!! ORDER FOR SORTING, for space is reserved word: space; don't use 2-letters characters like 'ch', 'ae' etc. !!!
sINIT="space A a Á á B b C c Č č D d Ď ď E e É é Ě ě F f G g H h I i Í í J j K k L l M m N n Ň ň O o Ó ó P p Q q R r Ř ř S s Š š T t Ť ť U u Ů ů Ú ú V v W w X x Y y Ý ý Z z Ž ž"


# array with sorted letters
gpi=[] # array for branches
len_stack=1 # depth of stack for no recursion

def supposed_chars(): # get the array from supposed characters in sINIT
    global sINIT
    if (sINIT==""):
        print("empty sINIT, the space was as know character")
        sINIT="space"
    p1=sINIT.split(" ")
    try: # change reserved word space to " "
        p1[p1.index("space")]=" "
    except:
        pass
    return p1


def treesort(p):
    global gpi, sINIT, len_stack


# 0) prepare the array with SUPPOSED characters from sINIT
    print("   supposed characters from sINIT")
    amax=0 # number of maximal used Ascii code
    amin=65536 #=&FFFF for utf-8 # minimum used Ascii code
    pb=[0]*amin # array with marks if character is used

    p1=supposed_chars() # chars from sINIT
    icount=-1
    for x in p1: # current letter from sINIT
        a=ord(x) # Ascii code
        if (a>amax): amax=a # maximal used Ascii number
        if (a<amin): amin=a # minimal used Ascii number
        pb[a]=icount
        icount-=1

# 1) detect REALLY USED characters
    print("   detect really used characters")
    icount=abs(icount)
    for x in p:
        if ( len(x)>0 ): # current word
            for y in x: # current letter
                a=ord(y) # ascii code
                if (a>amax): amax=a
                if (a<amin): amin=a
                if (pb[a]==0):
                    pb[a]=icount #unknown character
                else:
                    pb[a]=abs(pb[a])

    # print(pb[amin:amax+1])
    imax=amax+1

# 2) create indexed array (muster, filter)
    print("   create filter")
    ptemp=[0]*imax # temporary array, now for numbers for sorting-order for supposed characters from sINIT
    punknown=[]

    # create sorting positions for used characters from sINIT + create array with unknown characters
    i=0
    iused=0 # count of used characters from supposed ones
    for x in pb: # current character
        if (x==icount): # it is unknown character
            punknown.append(i)
        elif(x>0):
            ptemp[i]=x # supposed character is used, so put the number for sorting-order
            iused+=1
        i+=1

    # put used characters to their sorting-positions
    p1=[0]*i
    p2=[None]*i
    i=amin
    j=0 # count the used characters
    while i<imax:
        if (ptemp[i]>0):
            p1[ptemp[i]]=chr(i)
            j+=1
            if (j==iused):
                break # last used char means end
        i+=1

    # put unknown characters to their sorting-positions
    ptemp=[]
    y=len(punknown) # unknown characters
    if (y>0):
        print("!!! " + str(y) + "x UNKNOWN character !!!")
        for x in punknown:
            a=chr(x)
            p1[icount]=a
            ptemp.append(a)
            icount+=1
        print(ptemp)

    # create gpi[]
    gpi=[0] # first element is for the Count ow word
    i=1
    for x in p1: # create array for branches
        if (x!=0):
            gpi.append(x)
            p2[ord(x)]=i
            i+=1

    # NOW: gpi[] has sorted all used characters, unknown ones are at the end (sorted as per their Ascii codes)
    # print(gpi) # array for branches
    # print(p2[min:max]) # array with indexes (filter)
    icount=len(gpi)
# 3) build the tree
    startTime=time.time()
    print("   building the tree")
    tree=[None]*(len(gpi))
    tree[0]=0 # count of all words in tree
    for s in p: # current word
        ilen=len(s)

        if (ilen>len_stack): len_stack=ilen # find the longest word for no recursion stack

        ilen2=ilen-1
        level=tree # current branch for loop
        j=0
        while j<ilen: # go through characters in word
            s1=s[j] # current letter
            # add array to the tree
            index=p2[ord(s1)]

            if ( isinstance( level[index], type(None) ) ): # still no character in cell in branch
                if (j==ilen2): # last character from word, so it means end of word
                    level[index]=1 # put only number
                    tree[0]+=1 # increase the count of all words
                else:
                    p3=[None]*icount # new branch with empty values
                    p3[0]=0 # count is 0; but the sub-branch is
                    level[index]=p3 # add new branch to tree
                    level=level[index] # take new branch
            elif ( isinstance( level[index], list) ): # the letter is in branch
                if (j==ilen2): # last character from word, so it means end of word
                    level[index][0]+=1 # increase the count of word
                    tree[0]+=1 # increase the count of all words
                else:
                    level=level[index]
            else:
                p3=[None]*icount # new branch with empty values
                p3[0]=level[index] # count is moved to new branch
                level[index]=p3 # add new branch to tree
                level=level[index] # take new branch

            j+=1 #next j

# 4) read the tree
    print("   " + str(time.time() - startTime))
    startTime=time.time()
    print("reading the tree")

    # no recursion
    p=non_recursive(tree, gpi) # last no recursion, FUNCTIONAL

    print(p)

# 5) write the time
    print("   " + str(time.time() - startTime))

# 6) test if word exists or not
    print("\nTest if word exists:")
    word="head-overflow" # <== WORD you want to test
    word="BAOBAB"

    s="tree"
    for x in word: # create the expression for eval
        s=s + "[" + str(p2[ord(x)]) + "]"

    # print(s) # maybe you will also see the [None] in indexes, so it means the word has some characters that aren't used in whole input data

    bOK=True
    try: # test if indexes exists in array
        x=eval(s)
    except: # error, so it means there isn't some index in array of arrays :-)
        bOK=False

    bexist=False
    if (bOK==True): # indexes exist in array, so check the count of word
        if ( isinstance( x, type(None) ) ):
            pass
        elif ( isinstance( x, list ) ):
            if (x[0]>0): bexist=True
            else: bexist=False
        elif ( isinstance( x, int ) ):
            if (x>0):
                bexist=True
        else:
            pass

        if (bexist==True): # YES
            print("\n" + word + " -> YES, exists\n")
        else: # NO
            print("\n" + word + " -> NO exists\n")

    else: # NO, there was error in try/except
        print("\n" + word + " -> NO exists\n")


# ============================= NON_RECURSIVE ===================

# to move from fixed size stack to the use of append ... 4 places only
# now using fixed size stack
# letting prints for ctrl but commented

def non_recursive(tree,gpi):

    # array to store the list of the words
    words = []

            # depth of stack is like the longest word
    stack = [[0,"",[]]]*(len_stack+1) # my test, if bug then *10 and uncomment lines in: # stack size increasing if necessary

    # starting data
    subtree = tree
    ne = 1
    out = ""

    # initial stack step
    pstack = 0
    stack[pstack] = [ne,out,subtree]

    # size of gpi is the same for the lists
    last = len(gpi)

   # principal loop on the stack (acessing sublevels of the tree)
    while pstack != -1:

        ne,out,subtree = stack[pstack]

        # loop in a level (depending of gpi size)
        while True:

            if ne == last: break

            if not isinstance(subtree[ne],type(None)):

                # new list found
                if isinstance(subtree[ne],list):
                    out += gpi[ne]

                    # new list/level
                    subtree = subtree[ne]

                    # word completed
                    if subtree[0] != 0:
                        words.append(out)

                    # prepare to continue at that point when ending the new list
                    stack[pstack][0] = ne + 1

                    # next position in the stack
                    pstack += 1

                    # stack size increasing if necessary
                    # if pstack == len(stack):
                    #     stack2 = [[0,"",[]]] * 10
                    #     stack += stack2

                    # store atual data in the stack
                    stack[pstack] = [1,out,subtree]
                    break

                else:   # int found in the list
                    words.append(out + gpi[ne])

            # next position in the stack
            ne += 1

        # end of the current list reached
        if (ne == last):
            pstack -= 1

    return words


def loadFileString(sUrl):
    with open(sUrl, encoding="utf-8",) as f:
        ss=f.read()
        f.close()
    return ss.splitlines()


def randgen(qty,gpi):
    # not generate largest words
    maxsize = len(gpi)//2
    p = [""]*qty
    for n in range(qty):
        nbChar = random.randint(2,maxsize)
        s = ""
        for nc in range(nbChar):
            r = random.randint(1,len(gpi)-1)
            s += gpi[r]
        p[n]=s
    return p


def main():
    global len_stack
    # set the variable p[] from standard array; or from file; or from generate_big_array()
    p=["head", "over", "(p", "!N", "BAOBAB", "[B", "b", "a", "AA", "GRAZL", "AA", "BABA", "BA", "OBA", "OB", "BOB", "BOA", "A%", "A!", "ZLO", "AAA", "AH", "AHOJ", "AHU", "AHA", "AH", "AA", "GRAZL", "flow", "AA", "AAB", "CACO", "CACORA", "CHAMRAD", "CMUCHACI", "CHECHOT", "VOCHECHULE", "VOCHMELKA", "SMRADOCH", "SVOLOC", "TUPEC", "JASON", "BURIC", "DRSON", "BLIVAJZ", "LEMRA", "CUMIC", "ZVANIL", "GRAZL", "JASON", "BURIC", "DRSON", "BLIVAJZ", "BLIVAJZ", "LEMRA", "CUMIC", "BAB", "CAB", "BABOVKA", "BAB", "CAB", "BABIZNA", "AAA", "AA", "BB", "AAA", "AA", "AA", "AAA", "AA", "A", "B", "BB"]

    #p=randgen(1000, supposed_chars())

    p=loadFileString("d:/ff.txt") # <== your file here (each line is taken like one word)

    startTime=time.time()
    print("treesort is running")
    treesort(p)
    print("treesort total: " + str(time.time() - startTime))

main()

Možná někoho napadne proč je to napsané tak jak to je a že prý by to v tom Pythonu šlo lépe, ladněji apod. To možná ano, ale můžete si být jisti, že mě ten, jak občas říkávám pitomej pajtn, fakt nebaví a nesedí mi. A byl jsem rád že jsem v tom dokázal s pomocí udělat funkční verzi, ale když už v tom nikdy nic dělat nebudu, budu jedině rád.

Rychlejší zápis stromu?

Ten by měl být když se znaky nebudou převádět na Ascii kódy ale soubor se bude načítat binárně a pracovat se s načtenými hodnotami bude rovnou jako s čistými integery. Nicméně i dále v ukázkách je to přes Ascii kódy. Může na to být vhodné klasické C/​C++, neb tam může být velká výhoda v možnosti vlastní správy paměti.

Rychlejší čtení stromu?

Možno využít ukazatele na větve podobně jako v TreePackingu a nemuselo by se při vypisování kontrolovat spousta prázdných indexů. Jenže znamená to dělat ukazatele buď při vystavování stromu, což by tu fázi nějak prodloužilo; nebo třeba postupně až při různých čteních stromu, což by první uživatelé sice ani nepostřehli, ale zase by tam byly nějaké podmínky navíc typu teďČtiPostupněPoIndexech, teďHopsniRovnou apod., což může už zase zdržovat když už by byl strom napointrovaný a tyto podmínky by tak byly zbytečné. Nezkoušel jsem, nicméně poté se nabízí i expertní varianta měnit kód programu za běhu a ty podmínky z toho pak vyhodit :-).

S vícepísmenky

Předchozí výsledné řazení ale nebude úplně fungovat pro českou abecedu, neb nerozlišuje ch. To se dá zajistit větvemi na vstupu, což je už trochu těžší.

A také se dá osekat velikost písmen, přičemž stejně by se dala otesat i diakritika:

Zase ta RAMka

Je vidět že nějaké přečnívající větve by šly uříznout, čímž by se ušetřila RAMka. Strom by pak vypadal v podstatě následovně (uvedeno bez pomocných písmen neb vše je jen dle indexů).

Je však možné vytvořit variantu která nebude mít ve větvích žádné prázdné místo, byť pak je potřeba někam přidat informaci o kterou větev jde, např. rozšířit nultý index. V ukázce však řešeno barvami:

Pak je otázka jestli strom nejdříve vytvořit a pak mu optimalizovat větve – což pokud se šetří RAM tak nevyznívá moc dobře; nebo mu vytvářet optimalizované větve již za chodu – což chce další strom či větve pro prohledávání seznamu již vytvořených větví :-). Větve by pak musely být všechny indexovány a rozhodně by to bylo pomalejší, anebo mnohem víc na hlavu při vymýšlení té dynamiky ať již v něčem neinterpretovaném či dokonce ve vlastní správě paměti.

A proč pořád skrblit RAMku? Protože to je skvělá struktura pro databázi, stačí přidat odkazy na věty ze kterých byla slova do stromu zahrnuta a je hotové vyhledávání bez neustále opakovaného prohledávání hromady stejného textu.

Což se dá využít ale i třeba když víte že budete opakovaně vybírat položky z nějakého asociativního pole, kdy narozdíl od hashovacích tabulek není potřeba žádné prapodivné propočítávání a nehrozí kolize.

Stromové vyhledávání (TreeSearch)

Pár vět pro ukázku i s naznačenými odkazy na ně ze stromu:

Jelikož do buňky ve větvi lze nalinkovat vše možné, tak lze vytvořit strom třeba jen z malých písmen bez diakritiky, např. jakožto a by byla brána áčka a A á Á, ale možno i ä. Nebo jakožto e by bylo bráno: e E é É ě Ě. Takže může být vyhledáváno slovo bez diakritiky v datech s diakritikou.

Bezdiakritický strom může mít ve větvích slovo rad, ale linky půjdou na slova rad (mnoho rad) i raď i rád i řád i řaď i (mnoho) řad.

Indexace na původní data zabere opět víc RAMky, ale v případě že se data prohledávají opakovaně je rychlost dohledávání ohromující.

Následující příklad jde spustit v Pythonu a v konzoli poté dát vyhledat rad nebo rad*. V prvním případě vypíše věty jen se slovem rad, ve druhém jde o vyhledávání ignorující diakritiku i velikost písmen, tudíž vypíše více vět.

'''run this file and try to search rad or rad*. Or change the parameters for function main() in last lines of this file to load data from your TXT file (where one line is taken as one sentence)
- it will create the Tree and then you can try to search the sentences in Python Console, word ended by star (word*) is for simplified searching (that ignores the upper/lower-cases and diacritics marks)
- the Tree is built from simplified words, so there is Czech alphabet in variable SUBSTITUTES transformed to lowercase English alphabet'''

# if you want to see the size of Tree, install the package 'pympler' and uncomment last 2 lines in function main(), but really it isn't fastest process


import time

IUTF=65536 # the count for UTF-8 (0x10FFFF for Full UTF-16)

# no-substituted characters for a words in tree
SINGLETONS=["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]

# substituted characters ["Find", "Replace"] to simplify the words
SUBSTITUTES=[ ["A", "a"], ["B", "b"], ["C", "c"], ["D", "d"], ["E", "e"], ["F", "f"], ["G", "g"], ["H", "h"], ["I", "i"], ["J", "j"], ["K", "k"], ["L", "l"], ["M", "m"], ["N", "n"], ["O", "o"], ["P", "p"], ["Q", "q"], ["R", "r"], ["S", "s"], ["T", "t"], ["U", "u"], ["V", "v"], ["W", "w"], ["X", "x"], ["Y", "y"], ["Z", "z"], ["á", "a"], ["č", "c"], ["ď", "d"], ["é", "e"], ["ě", "e"], ["í", "i"], ["ň", "n"], ["ó", "o"], ["ř", "r"], ["š", "s"], ["ť", "t"], ["ú", "u"], ["ů", "u"], ["ý", "y"], ["ž", "z"], ["Á", "a"], ["Č", "c"], ["Ď", "d"], ["É", "e"], ["Ě", "e"], ["Í", "i"], ["Ň", "n"], ["Ó", "o"], ["Ř", "r"], ["Š", "s"], ["Ť", "t"], ["Ú", "u"], ["Ů", "u"], ["Ý", "y"], ["Ž", "z"], ["-", ""], ["~", ""], ["ـ", ""] ]

INFO=[0]*IUTF #info about used characters: <=-1 separator; 0 char isn't use; >=1 index in filter
SEPARATORS=[] #really used separators
FILTER=[0] #characters in branch
REPLACEMENTS=[None]*IUTF #array with replacements for simplification of letters

def initFilter(primalData):
    '''create the list of simplified sentences; + array with only really used characters; + array with only really used separators'''
    global IUTF, INFO, SEPARATORS, FILTER, REPLACEMENTS, SINGLETONS, SUBSTITUTES

    for character in SINGLETONS:
        REPLACEMENTS[ord(character)]=character #put singletons to root
    for character in SUBSTITUTES:
        REPLACEMENTS[ord(character[0])]=character[1] #put substitutions to root

    output=[]
    indexInfo=1 #plus index in INFO
    for line in primalData: #current line from primal data
        sentence=[] #array for simplified sentences
        wordSimple=""
        for letter in line: #current character
            ascii=ord(letter) #ascii code
            replacement=REPLACEMENTS[ascii] #replacement for character
            if isinstance( replacement, type(None) ): #there isn't substitution for character
                if wordSimple!="": #word is empty if there was sequence of more separators in string
                    sentence.append(wordSimple)
                    wordSimple=""
                INFO[ascii]-=1 #character is separator

            else: #there is substitution for character
                letterSubst=replacement #substitution instead original letter
                if letterSubst!="":
                    wordSimple+=letterSubst #add substitution to word
                    asciiSubst=ord(letterSubst)
                    if INFO[asciiSubst]==0:
                        INFO[asciiSubst]=indexInfo #add index to filter with new character from substitution
                        indexInfo+=1

        if wordSimple!="": #last word
            sentence.append(wordSimple)

        output.append((sentence)) #add sentence to output (including empty sentence because there can be empty lines in TXT file)

    #create array for filter and separators
    FILTER=[0] #first cell is reserved for zero index (links to primal data)
    ascii=0
    for number in INFO: #create filter for branch and array with separators
        if number>0:
            FILTER.append(chr(ascii))
        elif number<0:
            SEPARATORS.append(chr(ascii))
        ascii+=1

    return output


def treefire(sentence):
    '''get 1st simplified word from sentence'''
    global REPLACEMENTS
    wordSimple=""
    for letter in sentence:
        ascii=ord(letter) #Ascii code of letter
        replacement=REPLACEMENTS[ascii] #replacement for character
        if not isinstance(replacement, type(None)): #there is replacement for letter
            wordSimple+=replacement
        elif wordSimple!="":
            return wordSimple

    return wordSimple


def treeInit(simplifiedSentences):
    '''create the tree from the list of simplified words, with the links to primal data'''

    icount=len(FILTER) #count of cells in branch
    tree=[None]*icount
    tree[0]=0 #count of all words in tree
    link=0 #link with index to primal data (the number of primal sentence, the numbering starts from 0)
    for sentence in simplifiedSentences: #current simplified sentence
        for wordSimple in sentence: #current simplified word
            iLen=len(wordSimple)
            branch=tree #current branch
            iPos=0 #position of character in word
            while iPos<iLen:
                index=INFO[ord(wordSimple[iPos])] #index in branch for current letter

                if isinstance(branch[index], type(None)): #empty cell in branch
                    branch[index]=newBranch(icount) #add new sub-branch to tree
                    if iPos==iLen-1: #last character from word, so it means end of word
                        branch[index][0]=[link] #put 1st link to zero index
                        tree[0]+=1 #increase the count of all words
                    else: #character isn't last in word
                        branch=branch[index] #take sub-branch

                elif isinstance( branch[index], list): #letter is in branch
                    if iPos==iLen-1: #last character from word
                        if (branch[index][0]==[]) or (branch[index][0][-1]!=link): #zero index in sub-branch is empty or current link isn't same like last inserted link
                            branch[index][0].append(link) #add link zero index
                        tree[0]+=1 #increase the count of all words
                    else:
                        branch=branch[index] #take sub-branch

                else:
                    branch[index]=newBranch(icount) #add new sub-branch to tree
                    branch=branch[index] #take new sub-branch

                iPos+=1 #next character in word

        link+=1 #index for sentences

    return tree


def treesearch(tree, primalData, word): # the parameter 'tree' in this function is called only via eval()
    '''search the words in tree'''
    sEval="tree"
    for letter in treefire(word): #create the expression for eval() to detect simplified word in tree, for example: sEval=tree[3][1][8][6]
        sEval+="[" + str(INFO[ord(letter)]) + "]"

    output=[]
    bOK=True
    try: #eval() is OK
        branch=eval(sEval)
        if isinstance(branch, type(None)): #branch exists but has only empty cell and no sub-branch
            bOK=False
        elif isinstance(branch[0], list): #zero index with links to primal data
            primalSentences=[]
            for link in branch[0]: #get primal sentences
                primalSentences.append(primalData[link])
        else:
            bOK=False
    except: #eval() error, so it means there isn't some index in array of arrays :-)
        bOK=False

    if bOK: #search exact word in primal sentences
        if word[-1]=="*": # ssearching with simplified word
            output=primalSentences #all sentences with simplified word
        else: # searching with exact word
            iLen=len(word)
            for sentence in primalSentences:
                if testWordStartEnd(sentence, word): #test the start/end of sentence for exact word
                    output.append(sentence)
                elif iLen<len(sentence): #test middle of sentence
                    iPos=1 #the start position for searching the exact word in sentence
                    while True:
                        try:
                            iPos2=sentence.index(word, iPos) #real position of exact word in sentence
                            if (INFO[ord(sentence[iPos2-1])]<0): #letter before word is separator
                                if (INFO[ord(sentence[iPos2+iLen])]<0): #letter after word is separator
                                    output.append(sentence)
                                    break
                                else: #letter after word isn't separator
                                    iPos=iPos2+iLen+2 #so nearest separator can be at position +2 after word
                            else:
                                iPos=iPos2+iLen+1 #new search will be from one letter after found word because separators are controlled one position back
                        except: #exact word isn't in sentence
                            break

        if len(output)<1: #no sentences in output
            bOK=False

    t=time.perf_counter() # searched time
    # show output
    if bOK:
        print(word + " -> ", output)
        return len(output), t
    else:
        print(word + " -> NO exist")
        return 0, t


def testWordStartEnd(sentence, word):
    '''test start/end of string for exact word + separator'''
    iLen=len(word)

    #test start of string
    if sentence[:iLen]==word: #exact word is at start of string
        if (len(sentence)==iLen) or (INFO[ord(sentence[iLen])]<0): #exact word is string, or separator is after exact word
            return True

    #test end of string
    if (sentence[-iLen:]==word) and (INFO[ord(sentence[-iLen-1])]<0): #exact word is at end of string and the character before exact word is separator
        return True

    return False


def newBranch(icount): #zero index can be added to new branch
    '''add new branch to tree'''
    newBranch=[None]*icount #new branch with empty values
    newBranch[0]=[] #no links to primal data in new branch
    return newBranch


def main(url="", encode="utf-8"):
    '''find word in primal data (= in default array or some file)'''
    global INFO, FILTER, SEPARATORS, REPLACEMENTS

    t0=time.perf_counter() #start time
    print("load primal data")

    if (url!=""): # load data from txt file
        import os.path
        if (os.path.exists(url)): # file exists
            with open(url, encoding=encode) as f:
                lines=f.read()
            primalData=lines.splitlines() # sentences from file
        else:
            print("NO EXIST ->", url)
            exit()
    else: # short test array
        primalData=["á", "Á", "a", "A", "a A", "má mne rád či nemá tě rád", "dvojřad do dvou řad", "ŘAĎ TO SEŘAZENĚ", "mnoho rad mnoho chyb", "správně raď", "Řád naprd"]

    p=initFilter(primalData)
    t1=time.perf_counter()
    print("create filter: ", "%.2fms" %((t1-t0)*1000))
    tree=treeInit(p)
    t2=time.perf_counter()
    print("build tree: ", "%.2fms" %((t2-t1)*1000))
    print("separators:", SEPARATORS) # show really used separators (for sure)

    while True:
        searchedWord=str( input("\nword/word* to search (Enter=exit): ") ) # normal word is for exact searching, word* (ended with *) is for simplified searching
        if (searchedWord==""): # exit searching
            break
        else:
            t0=time.perf_counter()
            count, t1 = treesearch(tree, primalData, searchedWord) # count of found sentences and searching time
            print("sentences:", count) # show count of found sentences
            print("searching:", "%.2fms" %((t1-t0)*1000))


    '''see the size of Tree, but it need installed the package: pympler'''
    # from pympler import asizeof
    # print("Tree size:", "%.2f Mb" %(asizeof.asizeof(tree, code=True)/1000000) )


'''run'''
# main("d:/test.txt", "utf-8") # search in txt file
main() # search in short test array defined in function main()

Les

To je též možnost, kdy první strom je třeba bez diakritiky, ale odkazuje na další stromy které již mají dané slovo rozdiakritikované. Např. by se hledalo řaď, přičemž do prvního stromu by šlo rad a z něj link na další strom který byl byl složený již jen z rád, rad atd.:

Příroda

Je však možné přidat do stromu všechny části všech slov, například na slovo AHOJ by vedly indexy z AHOJ, AHO, AH, A, HOJ, HO, H, OJ, O, J. A udělat to i pro všechny kombinace velkých malých písmen i pro všechny kombinace znaků s diakritikou či bez ní. Může to vzít hodně RAMky, ale pak lze vyhledávat i dle částí slov.

Testování v praxi

Indexuje-li se seznam vět, je třeba mít nadefinované které znaky půjdou do stromu jakožto znaky které budou moci být vyhledávány, a které budou ignorovány. Někdy je asi lepší udělat ten seznam vyhledávaných znaků, někdy ten ignorovaných.

V případě že je strom staven z jedné univerzální větve, tak nemá moc smysl indexovat do něj více jazyků – setkal jsem se s dotazem proč prostě neberu větev rovnou jako 65 536 dvoubajtových znaků když by tam byla latinka i arabština. Neb v těch větvích poté bude hrozně moc prázdného místa a spotřeba paměti by šla hrozně nahoru.

A třeba kdyby se měly do stromu naindexovat slovníky pro více jazyků, např. cs+en+ar, už by asi došla RAM. To je lepší mít třeba tři stromy pro tři jazyky.

Jinak spotřeba RAM v Pythonu na starším GNU/FDL cs/en slovníku byla pro strom asi 400MB, bez diakritiky asi polovina. Pro slovník českých slov z LibreOffice (přes milión slov) asi 500MB.

Rychlost vyhledávání

Ta je enormní. Bodejť by nebyla když se řetězce mezi sebou neustále tupě neporovnávají ani se nekalkulují do jakýchsi hešů, jen se skáče po indexech v polích a poté rovnou vypisuje seznam vět.

V praxi jedno prohledání cs+en slovníku zabralo v Pythonu asi 1,5s. Po "nastromování" které trvalo asi 3,5s (ve VSCodium, v Pyzo to bylo asi dvakrát pomalejší čili 7s) bylo vyhledávání již v mikrosekundách, přičemž Python jakožto interpretovaný je oproti např. C pomalejší snad až několikatisíckrát.

Výhody proti ÁÍčkám

Enormní rychlost; výpočetní i energetická nenáročnost; a když se nad tím přemýšlí a naprogramuje se to pořádně a neplýtvá se RAM, tak rozhodně i menší potřeba paměti. A všechno je to degubovatelné (krokovatelné), tudíž i normálně opravitelné! Též přesná data, žádné pravděpodobnosti vydávané za spolehlivé nebo alespoň prý spolehlivě dostačující, žádné mixy s náhodami! Ale ač to z obrázků může vypadat jednoduše, naprogramovat to tak snadné být vůbec nemusí.

Vlastní správa paměti

Zde nelze napsat nějaký jednoznačný postup, neb záleží na projektu a datech. Ale vzhledem k mnohdoucí třístavovosti jednotlivých buněk stromu lze použít třeba znaménkové longinty → a nuly mít pro neiniciované buňky, záporné hodnoty pro data, a kladné pro ukazatele na to kde začíná třeba další větev v paměti.

Příklad třeba na seznam měst a PSČ, vypadalo by to nějak takto, 100 atd. jsou adresy buněk, -33162 jednotlivá PSČ, 0 značí nepoužito.

Větev je z písmen ABCD, a např. městečko A má PSČ 33162. Ves B neexistuje neb 0. Vesnice C je kladná hodnota 120 čili na adrese 120 začíná větev a v první buňce je PSČ pro C což je tedy 35721. A město CB má PSČ 43003.

Čili když vím že na data stačí ty samé velikosti buněk co jsou potřeba na ukazatele, jdou tedy větve skládat do jedné dlouhé řady v paměti.

Ona je totiž také otázka, jak do iniciace proměnných zasahuje operační systém, jak moc to zpomaluje a jestli se mu dá nějak napříkazovat aby do toho nezasahoval, jen umožnil rychlý vznik nějakého jednoho bloku v paměti a pak už se do toho fakt vůbec nemontoval.

Pro generaci československých programátorů 40+ asi nebude těžké představit si že 4bajtové longinty jsou na PSČ přeci jen zbytečně moc dlouhé, neb v mládí asi absolvovali podobné programátorské začátky Karel/​Basic/​Pascal/​Asm/​C a tedy je nepřekvapí přímé přístupy do paměti, a asi trochu zbystří když se čísla budou motat někde kolem 65 tisíc (2^16). Nicméně malé vysvětlení pro ty kdo to neznají.

Když to uděláte fakt jak na nějakém jednočipu bez operačního systému i bez jakéhokoliv rozlišení datových typů, tak by to vypadalo nějak takto, pěkně po bajtech:

První bit je znaménkový čili + nebo -. A pak je to vždy po čtyřech bajtech, ale je vidět, že buňky s 0000 0000 jsou tam vícekrát a ty by mohly jít ušetřit.

Když to však neuděláte podle sebe ale podle typů proměnných programovacího jazyka, tak program musí mít někde označeno že na adrese 104 je čtyřbajtový znaménkový longint, a to samé na adrese 108 i 112. Tudíž budete mít ještě nějakou tu tabulku třeba s jednobajty pro typ proměnné a longinty pro adresy.

Když to bude vytvořené jako typované pole, tak to bude že na adrese 104–112 jsou znaménkové longinty, když to ale bude v nějakém intrepretu co umožňuje mixování různých položek v poli, tak pro každou buňku musí být uvedeno o jaký typ se jedná, jestli právě třeba jako znaménkový longint nebo třeba string apod., což pak záleží na optimalizacích toho jazyka a stejné položky v řadě by měly být spíš uvedené jako typové pole, ale vzhledem k automatickému přetypovávání to je zase pomalejší při vytváření, prostě se tam pořád nějak posedlostně musí být ujišťováno, jak to zrovna pořád je. A záleží jak moc se do toho spravování proměnných motá či nemotá operační systém, neb když se do toho motá, tak to bude samozřejmě pomalejší.

Teď však k optimalizaci, poštovních čísel asi není 2^31 (nikoliv 2^32 neb znaménkový bit 4bajtového longintu). Nevím kolik jich v Čechách je, ale dejme tomu že třeba 6 500. Takže si stačí vytvořit pole od nejnižšího po největší což je třeba 10 000 až 99 999. A v něm si naodkazovat že 10 000 je 1, 10 001 je 2, pak jich třeba několik nebude, pak až např. 10 953 což bude 3 atd. Na tyto indexy i se znaménkem stačí v pohodě 2bajty (a stačily by až do 2^15 což je 32 768 čísel). Na větev stačí malá česká abeceda a možná z ní i vynechat q nebo w (jestli se v názvech měst fakt nevyskytují), a případně jeden index nechat pro ch, byť tam bude zdržovací podmínka jaký znak následuje po c.

A odmínusované oranžové hodnoty představují indexy v prvním poli kde jsou skutečná směrovací čísla.

Co na to laik? To vypadá přeci skvěle, že? Půlka RAMky a může to frčet, ne? Je už nadšení? Je již vidina jak se to zaimplementuje do svého programu? A jak to bude najednou rychlý a jak to dotyčného pozvedne? A jak taky konečně budou pozvednuty ty chudinky ve světě a najednou se všechno zlepší a začne to bejt fakt skvělý? :-). Ona se taková nadšení dají shrnout i do slov: Další co si po první vidině myslel jak se třemi proměnnými dobude svět! Po čase pak platívá: Kde je nadšení, přijde vyhoření.

Ono je zde vícero úskalí. Co když počáteční adresa kde začíná strom nebude někde na začátku RAM, ale výše, takže v reálu třeba nikoliv na adrese 100, ale třeba až na adrese 28 423 178? To poté budete do ukazatelů psát 28 423 180, 28 423 182 atd? To se ale do těch 15-ti bitů nevejde :-(. Nicméně lze použít oblíbený kompresní postup jež je využíván třeba při optimalizaci eSVéGéček a to nahrazení absolutních hodnot za relativní, tedy zapamatovat si adresu začátku stromu a vědět délku větve, pak stačí psát čísla od 1 (2, 3 …) označující na kterou větev se ukazuje.

No jo, ale jak bude tedy větev dlouhá? A bude stačit 15 bitů zároveň pro odkazy na pole se směrovacími čísly a odkazy na větve? Kolik vlastně tedy bude větví?

Délka větve je jak vidno žádoucí co nejkratší, neboť to bude i jednodušší. Převést vše na malá písmena by mělo být bezproblémové a hned je přeci ušetřena půlka! Byť je to skutečně pravá půlka nebo jaxi nějak plusmínus půlka :-)? Velkých písmen je stejně jako malých, ovšem co kombinace pro ch → CH, Ch, ch, cH? To vypadá jak chyták, co když jich tam bude víc? Je to jedno, akorát když někdo tvrdí že to je matematicky přesně polovina, tak to bude tak akorát v nějaký jeho fakt nezáživný vidině v hlavě.

Takže je možná možné to zkrátit o q a w, ale to se musí ověřit na datech. Co to ch, vyplatilo by se zkrátit? Kolik jich je vůbec s ch? Třeba Chomutov, Chbany, Chlum … → a už tě také jistě napadají další, takže raději zkrátit, nikoliv c a h.

Co stejný názvy, např. Vysočany nebo Újezd? Mají to být Vysočany u Kotaneče nebo Vysočany u Oslnice? Nebo Újezd u Manětína či Plzně? Tak co s tím? Dát tam nějaký závorky, odkazy na jiný pole kde se to dotřídí? Přidat číslice ve stylu Hrádek1, Hrádek2, Hrádek3 …?

Co s těma 15-ti bitama? 2^15 je jen cca 32 tisíc a když to má bejt kladný a záporný tak asi 16 tisíc možností pro PSČ a 16 tisíc pro čísla větví. Ale kdeže! Když vím že PSČ je 6 500, tak od 1 do 6 500 je to index PSČ, a od 6 501 do 65 535 je to číslo větve; znaménkový bit by v případě nestejnýho počtu kladných a záporných zbytečně snižoval množství použitelných hodnot.

A kolik bude větví? No to už chce naprogramovat. Např. pro Chlumec je to 6 větví (ch, l, u, m, e, c), ale Chlum se vejde do Chlumce, takže podle počtu písmenek se to spočítat nedá. A kdo tvrdí že prý na základě matematiky jde nějaký dostačující odhad, tak nikdy nepracoval s všelijak různorodými daty a manifestuje jen nějakou nefunkční vidinu (či bezobrazně názor!). Jak to dopadá s vidinami již bylo příkladováno :-).

Vešlo by se to tedy do těch dvoubajtů nebo by byly potřeba trojbajty protože počet větví by byl větší jak cca 59 tisíc? Nevím, já to neprogramoval. A kdyby za pár let ubyla nějaká města nebo naopak přibyla? I to jsou otázky, na které je i sebelepší matematika k ničemu, pokud si tedy nehodláte ujíždět na nějakých dalších nereálných vidinách ve stylu ale-kdyby a nikam se nepohnout.

Jste-li laici, na domácím počítači vám skrblení RAM sotva přijde, máte třeba 16GB a řeknete si třeba že vám to stačilo i na nějakou sezónně zrovna největší hru. Ale něco jiného je to na nějakém serveru kde různých služeb a databází běží třeba mnohem více. A něco jiného třeba na webhostingu, kde na serverech běží třeba mnoho PHP pro mnoho hostů.

Stejně tak si možná říkáte, že není problém když vám aplikace nabíhá tři vteřiny než v ní začnete dělat, ale kdybyste to měli pustit desetkrát za sebou než se dostaví výsledek, za jak dlouho byste asi byli znechucení civěním do blba a otravným čekáním, kor kdybyste tuhle činnost absolvovali třeba 50× za den?

Asi i jako laickému programátorovi je vám jasné, že s tou vlastní správou paměti to není jen tak, a možná vám začne být i jasnější, proč začaly být vyvíjené i různé interpretované jazyky → mnohdy aby se ušetřilo práci s psaním složitého kódu, ovšem různě to nabobtnalo na mnohdy nepotřebných variantách ale-kdyby. Ať se však programuje v čemkoliv, je setsakra super když člověk ví jak to funguje, proč to dělá tak jak to dělá, proč jen tak a již ne ale-kdyby jinak, i co tím vlastně dělá :-). Vděk Aláhovi.

O chybě 134 vím, kdo si všiml tak má možná dobré předpoklady pro to dělat vlastní správu paměti :-). Když jde o čtyřbajtové buňky tak ta posloupnost u těch obrázků výše má samozřejmě správně být 128, 132, 136.

Jak jsem s tím začal

Angličtinu nijak extra neumím a v podstatě vůbec mě ten jazyk nebaví. Když jsem před lety psal nějaké en texty, překládal jsem to s pomocí programu ACS slovník který byl postaven na tehdejším GNU/FDL otevřeném en/cs slovníku. Ale štvalo mě, když mi to pro jedno vyhledané české slovo vypsalo více anglických slov a já nevěděl které zvolit, tak jsem po jednom ta anglická přepisoval do dalších oken programu abych k nim zpětně dostal zase česká. Vypadalo to nějak takto:

Např. pro slovo příklad to vypsalo exemplar, instance, paragon, example. A já chtěl aby mi to vyhledalo zpětně česká k těm vypsaným anglickým, což po přespání bylo:

exemplar → příklad

instance → žádost, případ, instance, výzva, příklad, prosba, situace

paragon → ideál, příklad, vzor

example → ukázka, vzor, příklad

Tenhle postup mi pomáhal lépe zvolit slovo, byť vzhledem k nekvalitě slovníku ne o mnoho jak jsem zjistil později. Ale pořád to bylo lepší než tupě tipovat. No a jelikož bylo strašně otravné psát pořád dokola ta jednotlivá slova, řekl jsem si, že bych to nějak zautomatizoval a udělal si na to program. Slovník byl otevřený, zdroják se slovíčky nebyl nijak zakódován a tak jsem se do toho dal. Něco jsem splácl v Pythonu a zjistil, že mu trvá asi vteřinu a půl než prohledá data na jedno slovo. Takže když slov bylo víc, tak to sice vypisovalo jak jsem chtěl, ale bylo to pomalé. Pak jsem žádal Aláha jak to udělat rychle :-). A za nějakou dobu mi začly chodit nápady s těmito algoritmy.

Ke konci roku 2022 jsem udělal první verzi TreeSortu v LibreBasicu (pro ty stromy strašná sebemrskačka), tehdy ještě přes rekurzi. V Poradně LibreOffice jsem to publikoval na začátku 2023 a žádal o pomoc s nerekurzívním čtením stromu. Pomohl mi Philippe Lévi z Paragvaje a začli jsme vytvářet pythonovskou verzi.

Dal jsem to i na Github, ale po čase to smázl. Neb jsem na Githubu nevnímal žádnou snahu o to, aby byl i v národních jazycích. Myslím že jsem se to tam i dočetl že prostě jen en (a prostě přístup: nauč se anglicky nebo máš smůlu!) Což nemá mojí podporu.

Vypadalo to dobře, a vyhledávání (nikoliv stavba stromu) bylo rychlé i v tom Pythonu, kterej ale fakt dokáže bejt nechutně složitej a nakonec vždycky pomalej.

Podle mě je ten prog. jazyk vystaven na myšlence: Chci mít vlastní programovací jazyk, ale nemám vlastní nápady! Takže to vždycky splychtit tak, že se použije něco z jiného jazyka a překombinuje se syntaxe, aby to nevypadalo jak čistý CtrlCV (a překombinovat nejlépe do jediné zbylé varianty kterou nikdo nepoužil neb je poněkud pochybná).

Ale zjistil jsem, že ten slovník byl v praxi k ničemu neb v něm bylo hodně chyb – to když jsem radil s makry jednomu Kanaďanovi a občas jsme si víc pokecali → to mi psal, že některý výběr slov je fakt špatný až nepochopitelný a že je to tak na 70%. Po tomto zjištění pro mě nemělo cenu pokračovat, neb jsem ještě dohledal původní informace o tom jak vznikal ten slovník (že od počátku nevadilo že tam budou chyby ale hlavně že prý bude), o tom že někteří přispěvatelé nesouhlasili se změnou licence apod. → z mého pohledu mix něčeho dobrého ale bohužel s různým sobectvím a ignorací, na čemž jsem se nehodlal podílet. Nebyl tedy důvod trápit se dál v Pythonu, čili větší pokusy než to že to funguje jsem nedělal. Takže raději si něco přeložím v DeepL nebo holt Gůgltrancce (notně pokročily oba, ale to proč mi to nevyhovuje by bylo na jinej článek), což bývá relativně pohodlné i když rozhodně ne bezchybné, ale ne tak strašné jako kdysi s tím slovníkem.

S Philippem jsme komunikovali angličtinou. A oba jsme několikrát těžce zažili stav který jsem nazval headoverflow [hed-ovr-flou] (inspirováno ajťáckým termínem stackoverflow - přetečení zásobníku), česky by to bylo přetečení hlavy, což však nevystihuje podstatu toho brutálního těžkého temna v hlavě v kterémž stavu nejde nic dělat (např. ani napsat jednoduchý email), pouze jen někam odpadnout.

Kdo někdy viděl nějaké fotky přetažených programátorů tak se jim asi pořádně zasmál, kdo to přetažení někdy absolvoval, asi se pořádně zabejčil, že něco takového už fakt nikdy nechce zažít!

Stěží představitelné struktury

Kdo pochopil o co v popisovaných strukturách jde, pomyslel si možná i že to nebude nijak těžké naprogramovat. Já si to též myslel, ale hedovrflouvů jsem přitom měl několik. A narážel jsem hlavně na neschopnost editorů nějak inteligentně vypisovat dlouhá pole – tedy tím stylem, že zobrazí třeba jen nenulové položky apod., nikoliv vše. Pár tisíc položek v poli a je hrozný pořád někde rolovat myší, a to i když je to rozdělený třeba na části po pár stovkách → to je pro ta vícerozměrná podpole ještě víc kontraproduktivní. A všelijaké proklikávání různých podpolí apod. s různými postupy v hlavě – fakt to nebylo tak snadné, neb to není jak zde na jednoduchých obrázcích.

Vybavuji si že Phelippe zkoušel i verzi která neindexovala celá slova ale pouze několik počátečních písmen, snad od dvou asi do osmi. Což ušetřilo RAMku a velmi redukovalo počet vět které se poté prohledávaly klasicky, tudíž výsledek byl vyhledán i tak velmi rychle. O tom že něco zřejmě podobného programoval asi před 40 lety se mi zmiňoval i Francouz A. J. Littoz z Poradny LibreOffice, přičemž jeho zkušenost myslím byla, že stačilo nalinkovat první dvě písmena a poté se vyhledávání zrychlilo i několikastonásobně. Jenže čeština má dost pestrých předpon a pro ní mi to nepřipadalo zrovna smysluplně nasaditelné.

Rozhodně jsou i rychlejší programovací jazyky na dynamická pole než Python, ale já nenacházím důvod proč bych se nějaký měl učit, nebo třeba oprášit po letech školní C/C++ a rozvinout se v tom (neb nějaká ta vlastní správa paměti je mi mnohem sympatičtější než různé interpretry). Ale na slovníky to použít nemohu, neb nemám k dispozici žádná kvalitní data. Na nějaké jiné věci bych si sice uměl představit využití, ale nejprve bych rád dodělal jiné věci co mám rozdělané.