TechBlog cikkei

Legnagyobb közös osztó-keresés

Hát ez nem pont egy technikai téma, inkább matek, de arra gondoltam, kiposztolom ide, hátha valakinek van ötlete. Szóval úgy néz ki, lassan szükségem lesz egy olyan algoritmusra, ami egy adott halmaznak megadja a legnagyobb közös osztóját. Ugye ha egész számokról van szó, akkor ez egy elég triviális probléma. A gond az, hogy nekem valós számokra kell elvégeznem a dolgot, és igazából nem is a szigorúan vett "legnagyobb közös osztóra" van szükségem (két irracionális szám esetén például lehet, hogy nincs is közös valós osztójuk), hanem valahogy arra a valós számra, ami egy egészséges egyensúlyt ad a következő két feltételre:

  1. Egy adott (valós) számhalmaz elemeit elosztva ezzel a bizonyos számmal a maradékok legyenek "kicsik".
  2. A halmaz elemeit ezzel a bizonyos számmal elosztva az eredmények legyenek "minél közelebb" olyan racionális számokhoz, amelyeknek a nevezője "minél kisebb".

És plusz pontért még egy kritérium:

  • A számhalmaz minden eleméhez lehessen rendelni egy "súlyparamétert", ami azt mutatja, hogy mennyire "gáz", ha ezt a bizonyos legnagyobb közös osztót ennek a számnak az "ignorálásával" határozzuk meg.

A konkrét megoldandó probléma az, hogy adott egy formáns-halmaz (vagyis: egy adott hangról készített "FFT-szkeccs", vagyis nem a teljes FFT kép, hanem csak a legjellemzőbb frekvenciák és a hozzájuk tartozó amplitúdók, mint "súlyfaktorok") és ezekből az adatokból meg kell határoznom, hogy milyen hang szól (pontosabban, hogy a mintavételezett spektrumnak mi az "alaphangja"). Az alaphang az a frekvencia, amivel a "legegyszerűbben" magyarázható a spektrum többi tagja.

Utóbbi alatt a következőt értem: ideális esetben egy (hangszer)hang spektruma modellezhető úgy, mint egy f0 alapfrekvencia és ennek fn=nf0 felhangjainak halmaza (n egész, vagy legalábbis olyan racionális szám, aminek a nevezője kellően kicsi). A gyakorlatban általában a mérési hibák, az adatfeldolgozás során bevitt egyéb hibák (pl. FFT-ablakolási problémák stb.) a környezet és a hangszerek nemlinearitása miatt ez a modell nem teljesen helytálló. Sajnos az irodalomban csak olyan képleteket találok alaphangbecslésre, amik erősen "mérnöki" jellegűek (pl. most olvastam egyet, ahol bizonyos hibákat ad össze bizonyos együtthatókkal, majd a képlet után közli, hogy "X és Y javaslata alapján az együtthatók legjobb értékei" majd jön egy rakás szám mindenféle indoklás nélkül), és valahogy nincs gusztusom ilyesmivel dolgozni, ezért gondoltam, hogy valamit összeütök magamnak, aminek egy ilyen "legnagyobb közös valós osztó keresés" lenne az első lépése.

Utoljára módosította SAdam 2010.VIII.30 11:57-n
Bejegyzés módosítása | PermaLink
Szavazás letiltva.

Hozzászólások

2

Descant 2010.VIII.30 13:35

NP problémának tűnik 1 blikkre


Wigy 2010.VIII.30 15:56

Ha jól gondolom, egyetlen hang alapharmonikusát keresed, mert az a hangszer nemlinearitásaitól (hangszín) függetlenül jellemzi a hangot. Ha egyszerre több hang is szól, akár meg is lehetsz lőve, mert a hangszer/keverés az alapharmonikusok összegének és különbségének a többszöröseit is ki fogja adni.

Elsőre egy négyzetes algoritmus jutott eszembe: a formáns halmaz összes párjához képeznék egy új halmazban 1-1 elemet: az új halmaz elemeinek frekvenciája a pár elemeinek frekvenciakülönbségének abszolútértéke lenne, az amplitúdója a pár elemeinek harmonikus (1/(1/a + 1/b)) közepe lenne.

Az új halmaz hasonlítana a régihez, de több eleme lenne, és kiszűr néhányféle zavart belőle. Az alapharmonikust szerintem úgy találod majd meg, hogy frekvencia szerint rendezve élesen el fog különülni az elején egy halmaz, amelyeket súlyozva átlagolsz, és megkapod a frekvenciát (ez egy kis statisztika innen).

Fontos lehet, hogy ez a módszer működhet [fantom mélyhangra] is, amelynél az alapharmonikus nincs is a mintában, de az ember odaképzeli a felharmonikusok alapján.

Tagek: