1 kB-on legtöbb eltárolható telefonszám?

Elektronika, Elektromos eszközök

Sziasztok

Egy AVR 1 kB EEPROM-jában szeretném a lehető legtöbb telefonszámot eltárolni.
Ehhez jó lenne tudni, hogy mekkora a világon előforduló leghosszabb telefonszám (ország előtaggal, körzetszámmal, mindennel együtt)?

A telefonszámon kívül még 1 byte-ra szükségem van.
Ha 15+1 byte-al számolok, 64 számot tudok eltárolni.

Ha a telefonszámot egy hexadecimális számként ábrázolom, akkor 6 Byte-on el tudok tárolni egy 14 jegyű számot (281 474 976 710 655 a legnagyobb ábrázolható szám) a +1 byte-al ez 146 telefonszámot jelent.

Jó lenne a teljes számokat eltárolni. De ha kompromisszumot kötök és csak 4 byte-on tárolom a számok utolsó 9 számjegyét (4 byteon a legnagyobb szám: 4 294 967 295), a +1 byte-al 204 számot tudnék eltárolni.

Szerk.:
Egyelőre ott tartok, hogy egy 15 jegyű szám tárolásához kell 6 byte + 2 bit (50 bit). Ha a +1 byte helyett beérem 6 bittel, akkor 7 byte-on megúszom a tárolást, így 146 számot és a hozzá tartozó változót tudom eltárolni.

Van valakinek jobb ötlete?

  • 4004 megtekintés

( kozel | 2016. 01. 08., p – 16:22 )

Eszembe sem jutna ilyet csinalni.
A megoldasokra viszont kivancsi vagyok :D

( janoszen v | 2016. 01. 08., p – 16:22 )

Sztem nezd meg a libphonenumber forrasat, az eleg sok infot fog adni.

--
Pásztor János
Sole Proprietor @ Opsbears
Development Lead @ IXOLIT

Ilyeneket találtam benne: 

    const MIN_LENGTH_FOR_NSN = 2;
    // The ITU says the maximum length should be 15, but we have found longer numbers in Germany.
    const MAX_LENGTH_FOR_NSN = 17;
    // We don't allow input strings for parsing to be longer than 250 chars. This prevents malicious
    // input from overflowing the regular-expression engine.
    const MAX_INPUT_STRING_LENGTH = 250;
    // The maximum length of the country calling code.
    const MAX_LENGTH_COUNTRY_CODE = 3;

Szerk.: A Wikipédiában ezt találtam:
"The International Telecommunication Union (ITU) has established a comprehensive numbering plan, designated E.164, for uniform interoperability of the networks of its member state or regional administrations. It is an open numbering plan, however, imposing a maximum length of 15 digits to telephone numbers."

( ricpet | 2016. 01. 08., p – 16:37 )

Én ezt megnézném:

https://en.wikipedia.org/wiki/Variable-length_quantity

Ezzel már jelentősen előrébb vagy, mintha minden telefonszámhoz 16 byte kéne. 15 jegyű számot már 8 byte-on tudsz tárolni, ha jól számoltam.

Persze még lehet lejjebb menni valamivel, ha olyan feltételezéseket teszel, hogy minden szám legalább n számjegyből áll, és akkor az első n számjegyet nem VLQ-ben, hanem normál valahány byte-os int-ként tárolod.

Ezzel az a baj, hogy 11 számjeggyel minimum számolnom kell.
Ezt 6 byte-on el tudom tárolni a fenti módszer szerint.
Ha azért feláldozok a 6. byte-ból egy bitet, hogy jelezzem, hogy van-e még további számjegy, akkor már csak 10 jegyű számot tudok tárolni, ami biztos, hogy kevés.
A másik baj vele, hogy a számokhoz való hozzáférést is megbonyolítja, mert mindig végig kell olvasnom az összes számot, nem tudok "seekelni" az adatokban, mivel nem tudom a "record" hosszt.

Szerk.: 6 byteon tárolható legnagyobb szám: 1 103 823 438 081
5 byteon + 7 biten tárolható legnagyobb szám: 38 671 548 673

:) jó is a pozitív hozzáállás.

Barátom húzott fel hasonló "gyömöszölőssel". Persze az az eset is érthető volt, mert a külföldi cég ahol dolgozott, 10 eurós tömegtermékbe szánta a dolgot és minden cent számított.

Végülis az opciók:
- belepaszírozol annyit, amennyit tudsz a jelenlegi mikrovezérlőbe
- vagy előre specifikálod, mennyinek kell beleférnie és ahhoz választasz tömör tárolás mellett megfelelő méretű mikrovezérlőt. Ha árérzékeny a dolog, akkor körbenézni hogy van-e például fajlagosan olcsóbb nagyobb tartósmemóriás eszköz. (akár 8 bites, akár ARM Cortex M0 palettából)

A pozitív hozzáállásért még egy tipp: programmemória is írható szoftverből a mai mikrovezérlőkben. Esetleg ide is be lehet írni, ez nagyobb.

( haspokember | 2016. 01. 08., p – 17:45 )

Eloszor is, a country calling code valoszinuleg 1 byte-on tarolhato (szerintem nincs belole 256 db).

Masodszor, van valami heurisztikad a telefonszamokra nezve? Pl. leggyakrabban hasznalt / legvaloszinubb country kod, area kod, esetleg fontosabb szamok (pl. segelyhivo). Ha van ilyened, es fontos a tarolokapacitas maximalis kihasznalasa, akkor erdemes Huffmann-kodot hasznalni, a heurisztikaddal kiegeszitve. Persze ez azert igenyel nemi extra fejlesztoidot, szoval csak akkor erdemes ezt megcsinalni, ha valaki kifizeti (vagy csak egy hobbiprojektrol van szo).

Ezek közül melyik az, ami nem esik a 30-49-el kezdődő tartományba? :)

Nekem nem kell szétbontanom a számot országkódra, meg körzetszámra, telefonszámra.
Az egész szám egyben kezelendő.
Ahol több jegyű az országkód, ott a szabvány szerinte kevesebb a telefonszám, vagy a körzetszám. Az összes hosszuk nem haladhatja meg a 15 számjegyet.
Link

" Az összes hosszuk nem haladhatja meg a 15 számjegyet."
Pont az általad linkelt forrásban van ez:
The ITU says the maximum length should be 15, but we have found longer numbers in Germany.

Azaz hiába 15 a limit az E.164 szerint, Németországban találtak hosszabbat is már.

"Nekem nem kell szétbontanom a számot országkódra, meg körzetszámra, telefonszámra.
Az egész szám egyben kezelendő."
Akkor miért jöttél itt az országkódokkal?
Másrészt ha elegendő neked valóban egy 15 decimális számjegyű szám tárolása (és mondjuk nem kell könnyen és gyorsan decimális számjegyenként hozzáférned), akkor 7 byte-nál hatékonyabb kódolásod nem lesz. Pontosabban ha akarsz bitbűvészkedni, akkor 50 biten fog elférni egy telefonszám.

Főleg azért, mert 49 biten ugyebár a legnagyob, amit tárolhatsz, az a 562949953421311, ez meg ugye nenm elég, hiszen van csomó 562-nél nagyobb előhívóval rendelkező szám, az ausztrálok is. Így mindenképpen 50 bit kell pontosan.

A nagy kérdés tényleg az: kell tudnod gyorsan decimális számjegy szerinti keresést csinálnod ebben a táblázatban (mert akkor számjegyenként kell tárolnod, BCD például), vagy nem kell? Akkor pedig a bináris a leghatékonyabb.

Mik a pontos igényeid? A gyors módosítás/visszakeresés binárisan is működik akkor, ha minden bejegyzés ugyanannyi bitet használ, de cserébe így lesznek bitjeid, amik nem kódolnak semmit, azaz pazarolsz.
Ha a feladat, hogy egy előre beégetett listát tárolj, akkor azt még akár RLE-vel is tömörítheted, vagy egyéb hatékonyabb tömörítési sémákat is használhatsz.
Mi a tipikus felhasználás? Mert akkor ahhoz lehet mondani hatékony tárolási módot.

Ez a feladat.

Ha beérkezik egy hívás, megnézem, hogy benne van-e a listában.
Ha nincs, hadd csörögjön, ha benne van, akkor megnézem, hogy mit kell csinálnom a hívás hatására (ezt a +1 byte tárolja).

Az első szám az "admin" száma, aki SMS-ben további számokat és a hozzá tartozó jogokat tudja felvinni, módosítani, ill. törölni (inaktiválni) tud számokat, vagy további admint tud felvenni.

A bináris tárolás 1 byte előnnyel jár a BCD-hez képest, de a 8 bites AVR-el nem biztos, hogy megéri matekozni azért azért a +14% kelyért.

"Eloszor is, a country calling code valoszinuleg 1 byte-on tarolhato (szerintem nincs belole 256 db)."
De van, jóval több van.
https://en.wikipedia.org/wiki/List_of_country_calling_codes
Itt a listában 274 elem van, és csomó listaelemben több calling code.
Másrészt az, hogy hány darab van belőle, meg ezek decimálisan hogyan ábrázolhatók, megint más kérdés. Például a balkánon 300 felettiek a calling code-ok, nem sorfolytonosak.

( Nyosigomboc v | 2016. 01. 08., p – 18:07 )

Felesleges eltarolni, egyetlen for ciklussal legeneralhato a vilag osszes telefonszama! :)
Egyebkent mi a feladat? Gondolom nem csak tarolni akarod.

Modositani mennyire akarod oket? Ha igen, akkor kulon-kulon is?
Ha vahogy megoldod a kb. egyenletes irast, akkor a flash-bol is hozzavehetsz plusz teruletet, abbol a legtobb AVR-ben joval tobb van, mint EEPROMbol (ha az 1k-bol es az elterjedtsegebol jol tippelek, es 328P-rol van szo, abban 32k van, ami mellett a kod kenyelmesen elferhet (*) ). Esetleg a telefonszamok lehetnek flash-ben, a hozza tartozo metaadatok (pl. a hosszuk, esetleg meg az az 1 byte-od) meg lehetnek EEPROMban.
Ahogy mar emlitettek, vannak kulon IC-k (pl. 24C sorozat), vagy beletehetsz SD kartyat is, arra meg aztan a vilag osszes telefonszama elfer (kulon-kulon is).

(*) Flash-re 10000 irast garantalnak, EEPROMra 100000-et, ami 10-es szorzo az utobbi javara. Flash-bol viszont tobb, mint 10x annyid van (kodmerettol fuggoen), szoval ha ertelmes modon hasznositod (wear leveling), hosszu tavon tobbet/eleg sokat kibirhat.

--
Is that a banana in your pocket, or are you just happy to see me?
Neither, it's my new iPhone.

Bejövő hívások alapján kell különböző reléket vezérelni.
A jogosultság SMS-el programozható. A +1 byte a jogosultságokat tárolja.
Módosítani tudnom kell az adatokat. Aktiválni ill. inaktiválni elég a számokat, amíg nem telt be a memória. Ha betelt, az inaktívakat felül lehet írni.

Igen, 328P-ről van szó. :)

Köszi a Flash ötletet, elgondolkozom rajta.

Nemtom a security mennyire szamit, de par VOIP szolgaltato tud a te szamoddal hivast kezdemenyezni. A mobiltarsasagok is a marcius 15-i havazasrol "BELUGYMIN" hivoszammal kuldtek SMS-t, szoval ha minimalisan is szamit a biztonsag (pl. garazsajto kinyitasa a relevel), a jogosultsagot ne csak a telefonszambol vedd!

--
Is that a banana in your pocket, or are you just happy to see me?
Neither, it's my new iPhone.

Visszahívod ha a listádban szereplő számról hívott, beolvasol egy szöveget, hogy nyomja meg az 1-es gombot, ha állítani akarja a relét, egyébként tegye le a hívást. Aztán DTMF ellenőrzés kell csak. Így nem tudnak a klónozott számmal semmit sem kezdeni, mert visszahíváskor az eredeti fog csörögni.

( Nyosigomboc v | 2016. 01. 08., p – 18:15 )

Amugy ha 16 hosszu lenne a telefonszam (es igy 16+1 byte lenne a trivialis - pl. ASCII - megoldas), annal meg a BCD is sokkal jobb (8+1 byte-tal). 0-9-ig lehetnek a szamjegyek, A-F-ig meg plusz karakterek is elfernek (pl. +,formazasnak space, zarojel, kotojel, #, ures karakter (vagy ami a veget jelzi)). Implementalni eleg gyorsan es konnyen lehet, es hasznalni is.

--
Is that a banana in your pocket, or are you just happy to see me?
Neither, it's my new iPhone.

7 byte-al már meg tudom oldani a 15 jegyű számot + marad 6 bitem.
A számot nem kell formázni, ömlesztve jó az. :)

Szerk.: A BCD-s ötletet ettől függetlenül lehet, hogy megfogadom.
Sokkal egyszerűbb dolgozni vele, mint a 256 hatványaival. :)

Az A-F rész pedig bőven elég az egyéb adatok tárolására.

(A 128 egyébként is szép kerek szám, nem úgy, mint a 146. :D)

Ha netán még nem írta senki: BCD helyett 7 bitben bekódolhatod 11-es számrendszer szerint kettesével a számjegyeidet. Ez köztes megoldás a bináris változó hosszúságú számábrázolás és a BCD között. A 11. érték ('a') lesz a számvégjel.
Ezzel a BCD-hez képest 14,26%-kal több szám fér bele.

1 kByte-ba 2048 számjegy helyett további 292.

A másik, amin elgondolkoznék: prefixcsoportosítás, ha flash-be egyben való beíráskor ismertek a számok.

1.pointer 1.tetszőleges hosszú kiemelhető prefix a fenti 11-es számrendszer kódolásban 2.pointer 2.prefix és 'a' prefixvég 3.pointer: 3.prefix ... majd az
1. pointertől kezdődnek a suffixek 11-es számrendszerben 7 biten

És ezzel sokat megtakarítasz. Hátrány: számcsere más prefixel futásidőben macerás, tehát ez utóbbi inkább egyben feltöltésre alkalmas.

A 11-es számrendszer előnyeit nem igazán értem. De ha 7 biten tárolok 2 számot, akkor kell 7x7 + 4 bit a 15 számjegy tárolásához. 7 byte /telefonszám és még marad 3 bitem egyéb infónak. az megint 146 telefonszám és elég hozzá shiftelgetni, nem kell nagy matek. Köszi az ötletet.

Nem ismertek a számok előre, csak az egyetlen admin szám a fix.

Semmit. Ez az a megoldás, ha 7 biten tárolsz 2 számjegyet. Viszont 15 számjegy tisztán binárisan log21015 = 15*ln(10)/ln(2) = 49.83, tehát 50 bit. Ekkor a 7 byte-ból marad szabadon felhasználható 6 bited, ami a jogosultságokhoz, vagy akármihez akár elég is lehet.

tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE

Közben van még egy gond, amin tűnődöm. Gondolom, a szám kezdődhet 0-val is, így az automatikus 0 kioltás nem megy. Amennyiben a 7 biten 2 számjegy ábrázolását választod, kell egy speciális kód, ami azt jelzi, az a két számjegy nem létezik. Praktikusan mondjuk legyen ez a 0x7f. Ezen felül kell még egy bit, ami azt jelzi, hogy az első számpáros felső helyiértékű számjegye létezik, vagy sem. Tehát már csak 2 szabad bited maradt.

Tisztán bináris tárolásnál lehet azt csinálni, hogy az első 1-es bittől értelmezzük a számot, de ez az 1-es bit nem része a számnak. Ekkor is kell még egy bit, amelyik azt jelzi, hogy az első decimális számjegy az része-e a számnak, vagy sem. Ezzel maradt tehát 4 szabad bited.

Tehát egyszerűbb kódot kapsz, ha számpárosokat tárolsz, ekkor 2 szabad bited marad. Némileg bonyolultabb a kód bináris ábrázolásnál - a decimális konverzió, pláne változó hosszra összetettebb -, ekkor marad 4 szabad bited. Kérdés, ez elegendő-e, vagy be kell-e áldozni mondjuk két-két telefonszámonként egy-egy byte-ot még flag-ek tárolására. Ha igen, úgy az egész tárban 136 telefonszám fér el.

Másik lehetőség, hogy veszel pici soros FLASH-t. Például az SST25VF080B egy 8 lábú, 1 MB-os (8 Mb-es) eszköz. Tudom, mert használtam. Elférne benne 139810 telefonszám. ;)

tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE

Szerintem elbeszélünk egymás mellett.

Én binárisan szeretném tárolni a telefonszámot.
Ha több, mint 15 számjegy, akkor csak az utolsó 15-öt, ha kevesebb, akkor teszek elé annyi 0-t, hogy 15 számjegy legyen.

Pl.:
+49 12 345 678 901 234-ból lesz
912345678901234

+36 123 456 789-ből
000036123456789

+36 62 123 456-ból pedig
000003662123456

Értettem, mire gondolsz. Azt mondtam, hogy ezek alapján a téma bevezetőjének végén általad írottakat javasolom, azaz full binárisan tárolj. Nyilván a konverzió picit macerásabb, de több szabad bited marad, és ahogy írtad is, így 146 számot tudsz tárolni.

tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE

Szerintem, ha 8 bites, akkor 255 a legnagyobb ábrázolható szám, ami hardware-ben támogatott. Engem az ilyesmi azért nem zavar, mert én mindig assembly-ben programozom mikrokontrollert, ott meg olyan adatstruktúrát találok ki, amilyet akarok. Ha éppen 7 byte-os, mi több, csak 50 bites számot, akkor azt. Nyilván C-ben nehezen szakad el a kész könyvtárak kínálta lehetőségektől, s prüszköl az ember, ha valami mást kell csinálnia.

tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE

( kovi | 2016. 01. 08., p – 21:43 )

itt jártam

--
Vortex Rikers NC114-85EKLS

( locsemege v | 2016. 01. 08., p – 21:55 )

Szerintem dinamikus hosszt használj valami vége jelzővel vagy elején hossz infóval. Nyilván így keresni lassabb benne, de 1 kB-on nagyon gyorsan végig lehet szaladni, tehát ez nem szempont. Ugyanakkor ez nem jó, ha gyakran cserélgetni kell a számokat, mert egyetlen szám cseréje is igen sok EEPROM írással jár.

tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE

( athila v | 2016. 01. 08., p – 23:21 )

höhö vadász te most szopni jársz ide?

( BaT | 2016. 01. 09., szo – 04:04 )

Nem tudom jelezte-e már valaki (hajnali 4-kor nincs kedvem végigolvasni a topicot, de ha ezt most nem írom le, holnapra elfelejtem), de a telefonszám nem egy szám, hanem számok sorozata. Az 1, a 01 és a 001 három teljesen valid, egymástól különböző telefonszám. Viszont azt kihasználhatod, hogy a telefonszámok prefix számok, vagyis az nem fordulhat elő, hogy pl. az 1 és az 10 is valid telefonszámok legyenek. Ilyen adatot fában érdemes tárolni, gondolom a +1 byte valamilyen metaadat, azt tárolhatod a fa leveleiben.

Egy számnál nincs is előnye, akkor a fa mint láncolt lista viselkedik, a pointerek miatt ezért többet foglal, mintha tömbben tárolnád. Az előnye akkor jön ki, amikor már viszonylag sok számod van, és a számok között gyakori, hogy azonos prefixszel rendelkeznek. Pl. ha magyarországi mobilszámaid vannak: +36201234567, +36207654321, +36301234567, akkor a fa valahogy így néz ki: 


3-6-2-0-1-2-3-4-5-6-7
  |   |
  |   +-7-6-5-4-3-2-1
  |
  +-3-0-1-2-3-4-5-6-7

Ezzel megspóroltad 6 digit tárolását.

A bináris adatstruktúrát hozzá még nem találtam ki, de érdekel a probléma, agyalok rajta. :) De alapvetően ha egy számot el kell távolítani, akkor meg kell keresni azt a pointert, ami már egyértelműen azonosítja a számot (pl. a fenti példában a 2. szám esetén a 0 -> 7 pointer) és azt eltávolítani, illetve a többi digit helyét üres memóriaként kezelni.

Oké, igazad van, ekkora kapacitás mellett valószínűleg nem fogja az overhead-et ellensúlyozni a megspórolt adatmennyiség. De egy hibrid megoldás már működhet, pl. az első 4-5 digit fában tárolva, a maradék egyszerű változó hosszúságú tömbként, bcd kódolással (egy byte két digit).

( Replaced | 2016. 01. 09., szo – 11:33 )

miert nem bcd?

--
NetBSD - Simplicity is prerequisite for reliability

( _Franko_ v | 2016. 01. 09., szo – 20:09 )

Mi az a use-case, amire használnád és fogalmad nincs, hogy milyen hosszú telefonszámokat kell tárolni? Biztos, hogy ennyire előre kell optimalizálni ("premature optimization is the root of all evil")? Biztos, hogy jó AVR-t választottál a feladathoz? Akkora sorozatról van szó, hogy a darabár különbség és a mennyiség szorzata miatt megéri a befektetett munka? Illetve: ez egy házi feladat vagy a való élet?

--
https://portal.gacivs.info