Besidubliuojančių eilučių šalinimo ir dažnių analizės įrankis – tai pramoninio lygio kliento naršyklėje veikiantis teksto deduplikavimo variklis, sukurtas programuotojams, duomenų bazių administratoriams, SEO analitikams ir duomenų mokslininkams. Skirtingai nuo paprastų skriptų, kurie pakimba apdorodami didelius sąrašus, mūsų įrankis naudoja tiesinio laiko $O(n)$ JavaScript Map maišos lentelę (angl. hash table) kartu su Unicode NFC kanoniniu normalizavimu. Jis akimirksniu pašalina pasikartojančias eilutes, išskiria tik dublikatus (uniq -d), suranda griežtai unikalius įrašus (uniq -u) ir sudaro pasikartojimų histogramas be jokio duomenų siuntimo į serverį.
Kaip veikia $O(n)$ maišos aibės (Hash-Set) eilučių deduplikatorius
Apdorojant serverio prieigos žurnalus (logus), el. pašto prenumeratorių eksportus, SQL pirminių raktų išklotines ar raktažodžių lenteles, besidubliuojančios eilutės iškraipo statistiką ir sukelia duomenų bazių įterpimo klaidas. Mūsų variklis vykdo deterministinį keturių etapų normalizavimo ir maišos konvejerį tiesiogiai jūsų naršyklės operatyviojoje atmintyje:
- 1 etapas – Rakto normalizavimas prieš maišą: Prieš palyginant, ar dvi eilutės yra identiškos, kiekvienai eilutei suformuojamas kanoninis palyginimo raktas. Įjungus Unicode NFC normalizavimą, išskaidytos diakritinių ženklų sekos sujungiamos į vieną kanoninį simbolį. Pasirinktinis paraščių apkarpymas (Trim) pašalina nematomus tarpus ir tabuliacijas eilutės pradžioje bei pabaigoje, kad atsitiktinis tarpas nesukurtų klaidingai unikalaus įrašo.
- 2 etapas – Raidžių registro suvienodinimas ir tuščių eilučių filtras: Kai išjungiamas jautrumas registrui (Case-Insensitive), palyginimo raktas paverčiamas mažosiomis raidėmis, tačiau išvesties lange išsaugomas pirmojo (arba paskutiniojo) sutikto įrašo originalus registras. Tuščios eilutės gali būti visiškai pašalintos iš sąrašo.
- 3 etapas – Vieno praėjimo maišos lentelės indeksavimas: Kiekvienos eilutės raktas įrašomas į atminties
Mapstruktūrą, kurioje saugomi trys rodikliai: pirmojo pasirodymo indeksas, paskutinio pasirodymo indeksas ir tikslus pasikartojimų skaitiklis c ≥ 1. - 4 etapas – Aibės išgavimas ir rikiavimas: Priklausomai nuo pasirinkto režimo, variklis grąžina visus skirtingus įrašus (c ≥ 1), tik besidubliuojančias eilutes ($c > 1$), griežtai vienetinius įrašus (c = 1) arba pagal dažnį surikiuotą histogramą (cmax → cmin).
Algoritminis sudėtingumas: $O(n)$ maišos lentelės prieš O(n2) ciklus
Dažna primityvių internetinių teksto valymo įrankių klaida – naudoti `Array.prototype.indexOf()` arba įdėtuosius `for` ciklus tikrinant, ar eilutė jau buvo sutikta anksčiau. Kadangi `indexOf()` kiekvienai naujai eilutei nuosekliai tikrina visą jau sukauptą masyvą nuo nulio, n eilučių apdorojimas pareikalauja n(n-1)⁄2 eilučių palyginimų – t. y. kvadratinio O(n2) laiko sudėtingumo.
Apdorojant 100 000 žurnalo eilučių sąrašą, O(n2) algoritmas atlieka apie 5 × 109 (5 milijardus) palyginimų ir kelioms minutėms užšaldo naršyklės langą. Tuo tarpu moderni V8 ar SpiderMonkey `Map` / `Set` duomenų struktūra naudoja deterministinę teksto maišos funkciją ir pasiekia amortizuotą $O(1)$ paieškos laiką vienai eilutei:
LaikasHash Set(n) = Σi=1n O(1) = O(n), Palyginimai100k ≈ 100 000Šis 50 000 kartų algoritminis pagreitis leidžia mūsų įrankiui deduplikuoti 50 000+ eilučių greičiau nei per 15 milisekundžių ir kartu išsaugoti pradinę eilučių tvarką.
UNIX uniq filosofija ir matematinės aibių operacijos
1973 m. Douglaso McIlroy sukurta klasikinė UNIX komandinės eilutės programa uniq buvo suprojektuota magnetinių juostų srautams, kur operatyvioji atmintis buvo itin ribota. Dėl šios priežasties standartinis POSIX uniq lygina tik gretimas eilutes (`line[i] == line[i-1]`), todėl inžinieriai privalo pirmiausia surikiuoti failą abėcėlės tvarka (`sort file.txt | uniq`). Tačiau išankstinis rikiavimas sugadina chronologinę žurnalų tvarką ir išdarko konfigūracinius failus.
Mūsų įrankis realizuoja visus pagrindinius POSIX uniq režimus naudodamas pilną atminties maišos lentelę, todėl išankstinis rikiavimas nebėra privalomas:
- Standartinis deduplikavimas (c ≥ 1): Atitinka garsiąją `awk '!seen[$0]++'` komandą. Kiekviena skirtinga eilutė išvedama lygiai vieną kartą išlaikant natūralią jos pasirodymo tvarką (arba paskutinio pasirodymo poziciją).
- Tik besidubliuojančios eilutės (
uniq -d, $c > 1$): Atmeta visas eilutes, kurios pasirodė tik kartą, ir grąžina tik tuos įrašus, kurie pasikartojo bent du kartus. Idealiai tinka ieškant dvigubų sąskaitų, pasikartojančių el. pašto adresų ar IP adresų ugniasienės žurnaluose. - Griežtai unikalios eilutės (
uniq -u, c = 1): Išveda tik tas eilutes, kurios neturi nė vieno dublikato visame sąraše. Naudinga lyginant du sujungtus sąrašus, kai norite rasti įrašus, esančius tik viename iš jų. - Dažnių histograma (
sort | uniq -c | sort -nr): Suskaičiuoja ir surikiuoja kiekvieną unikalią eilutę pagal jos tikslų pasikartojimų skaičių bei procentinę dalį, su galimybe vienu paspaudimu atsisiųsti CSV ataskaitą.
Unicode NFC kanoninis ekvivalentiškumas ir duomenų higiena
Apjungiant tekstinius duomenis iš macOS (HFS+/APFS failų vardų), Linux serverių ir Windows Excel lentelių, vizualiai identiškos eilutės dažnai turi skirtingą baitų reprezentaciją. Pavyzdžiui, macOS dažnai saugo lietuviškas ar kitas diakritines raides NFD (išskaidyta) forma (bazinis simbolis + kombinacinis diakritinis ženklas), o Windows ir žiniatinklio formos naudoja NFC (sujungtą) formą (pvz., ą, ė, ū kaip vieną kodo tašką).
Be Unicode NFC normalizavimo prieš maišos skaičiavimą, įprastas deduplikatorius tokias dvi eilutes laiko skirtingomis ir palieka vizualius dublikatus jūsų duomenų bazėje. Vykdydamas `String.prototype.normalize('NFC')` kartu su paraščių valymu ir registro suvienodinimu, mūsų variklis užtikrina matematiškai nepriekaištingą daugiakalbių sąrašų valymą.
Dažniausiai užduodami klausimai (DUK)
Ar dublikatų šalinimas pakeičia pradinę mano sąrašo eilučių tvarką?
Ne – pagal nutylėjimą įrankis naudoja Palikti pirmą sutiktą (išlaikyti tvarką) režimą, kuris tiksliai išsaugo pirminę unikalių eilučių seką. Jei pageidaujate abėcėlinio arba pagal ilgį surikiuoto sąrašo, tai galite pasirinkti Išvesties rikiavimo meniu.
Kuo skiriasi „Palikti pirmą sutiktą“ ir „Palikti paskutinį sutiktą“ režimai?
Pasirinkus Palikti pirmą sutiktą, eilutė lieka toje vietoje, kur ji buvo rasta pirmą kartą, o visi vėlesni jos pasikartojimai pašalinami. Pasirinkus Palikti paskutinį sutiktą, ankstesni pasikartojimai praleidžiami, o eilutė išsaugoma paskutinio jos pasirodymo vietoje – tai itin naudinga valant `.env` konfigūracijas, CSS taisykles ar chronologinius žurnalus, kur vėlesnė reikšmė perrašo ankstesnę.
Kaip surasti tik tas eilutes, kurios sąraše kartojasi?
Pakeiskite veikimo režimą į Tik dublikatai (uniq -d, kiekis > 1). Vietoj išvalyto sąrašo išvesties lange matysite tik tas eilutes, kurios tekste pasirodė du ar daugiau kartų – taip akimirksniu aptiksite pasikartojančius prekių kodus, el. pašto adresus ar dvigubus įrašus.
Kodėl dvi iš pažiūros vienodos eilutės nebuvo pašalintos kaip dublikatai?
Dažniausiai taip nutinka dėl nematomo tarpo eilutės gale, tabuliacijos simbolio, skirtingo didžiųjų/mažųjų raidžių registro arba išskaidytų Unicode diakritinių ženklų. Įsitikinkite, kad pažymėti nustatymai Apkarpyti paraštes ir Unicode NFC normalizavimas, bei nuimkite varnelę nuo Skirti didžiąsias ir mažąsias raides.
Ar mano sąrašai ir žurnalai siunčiami į serverį?
Niekada. Visas maišos lentelių sudarymas, rikiavimas ir dažnių skaičiavimas vyksta 100 % lokaliai jūsų naršyklės JavaScript aplinkoje. Jūsų konfidencialūs žurnalai, klientų el. pašto sąrašai ir konfigūraciniai failai niekada nepalieka jūsų įrenginio.