Merkkijonotyyppi
Tietojenkäsittelytieteessä merkkijonotyyppi ( englanniksi merkkijono "thread, string") on tietotyyppi , jonka arvot ovat mielivaltainen aakkosten merkkijono (merkkijono) . Jokainen tämän tyyppinen muuttuja ( merkkijonomuuttuja ) voidaan esittää kiinteällä tavumäärällä tai sillä voi olla mielivaltainen pituus.
Muistin esitys
Jotkut ohjelmointikielet asettavat rajoituksia merkkijonon enimmäispituudelle, mutta useimmilla kielillä ei ole tällaisia rajoituksia. Unicodea käytettäessä jokainen merkkijonotyypin merkki voi vaatia kaksi tai jopa neljä tavua edustamaan sitä.
Merkkijonotyypin koneesityksen tärkeimmät ongelmat ovat:
- merkkijonot voivat olla kooltaan melko merkittäviä (jopa useita kymmeniä megatavuja);
- koko, joka muuttuu ajan myötä – merkkien lisäämisessä ja poistamisessa on vaikeuksia.
On olemassa kaksi pohjimmiltaan erilaista lähestymistapaa merkkijonojen esittämiseen tietokoneen muistissa.
Merkkitaulukon esitys
Tässä lähestymistavassa merkkijonoja edustaa merkkijono ; taulukon koko tallennetaan erilliselle (palvelu)alueelle. Pascal -kielen nimestä , jossa tämä menetelmä ensimmäisen kerran otettiin käyttöön, tätä menetelmää kutsutaan Pascal-merkkijonoksi .
Hieman optimoitu versio tästä menetelmästä on ns. c-addr u -muoto ( englanninkielisestä merkkitasaisesta osoitteesta + allekirjoittamaton numero ), jota käytetään Forthissa . Toisin kuin Pascal-merkkijonoissa, tässä taulukon kokoa ei tallenneta yhdessä merkkijonotietojen kanssa, vaan se on osa merkkijonoa osoittavaa osoitinta .
Edut
- ohjelma sisältää jokaisena hetkenä tietoa merkkijonon koosta, joten merkkien loppuun lisääminen, merkkijonon kopiointi ja itse asiassa merkkijonon koon saaminen suoritetaan melko nopeasti;
- merkkijono voi sisältää mitä tahansa dataa;
- on mahdollista ohjelmatasolla valvoa poistumista linjarajoista sen käsittelyn aikana;
- on mahdollista suorittaa nopeasti operaatio, kuten "ottaa N:s merkki merkkijonon lopusta".
Haitat
- ongelmia mielivaltaisen pituisten merkkien tallentamisessa ja käsittelyssä;
- merkkijonojen tallennuskustannusten nousu - "merkkijonon pituuden" arvo vie myös tilaa ja suuren määrän pienten merkkijonojen tapauksessa voi merkittävästi lisätä algoritmin RAM-muistia koskevia vaatimuksia;
- rivin enimmäiskokorajoitus. Nykyaikaisissa ohjelmointikielissä tämä rajoitus on enemmänkin teoreettinen, koska tyypillisesti merkkijonon koko tallennetaan 32-bittiseen kenttään, mikä antaa merkkijonon maksimikoon 4 294 967 295 tavua (4 gigatavua);
- käytettäessä aakkosia , joissa on muuttuva merkkikoko (esim. UTF-8 ), koko ei tallenna merkkien määrää, vaan merkkijonon kokoa tavuina, joten merkkien määrä on laskettava erikseen.
Päättävä tavumenetelmä
Toinen tapa on käyttää "lopetustavua" [1] [2] . Yksi mahdollisista aakkosten merkkien arvoista (yleensä merkki, jonka koodi on 0) valitaan merkkijonon päätteeksi, ja merkkijono tallennetaan tavujonona alusta loppuun. On järjestelmiä, joissa tavua 0xFF (255) tai merkkikoodia "$" käytetään merkkinä rivin lopusta, ei merkkiä 0.
Menetelmällä on kolme nimeä - ASCIIZ (tai asciz, ASCII-merkit , joissa on nollapäättävä tavu), C-merkkijonot (menetelmää käytetään yleisimmin C -kielessä ) ja nollapäätteinen merkkijonomenetelmä .
Edut
- lisäpalvelutietojen puuttuminen rivistä (lukuun ottamatta viimeistä tavua);
- kyky esittää merkkijonoa luomatta erillistä tietotyyppiä;
- ei rajoituksia enimmäislinjan koolle;
- taloudellinen muistin käyttö;
- merkkijonoliitteen saamisen helppous;
- merkkijonojen välittämisen helppous funktioille (osoitin ensimmäiseen merkkiin välitetään);
Haitat
- operaatioiden pitkä suoritus merkkijonojen pituuden ja ketjutuksen saamiseksi;
- keinojen puute ohjata linjan lähtöä, jos viimeinen tavu vaurioituu, mahdollisuus vahingoittaa suuria muistialueita, mikä voi johtaa arvaamattomiin seurauksiin - tietojen katoamiseen, ohjelman kaatumiseen ja jopa koko järjestelmään;
- kyvyttömyys käyttää lopettavaa tavumerkkiä merkkijonoelementtinä.
- kyvyttömyys käyttää joitakin koodauksia, joiden merkkikoko on useita tavuja (esimerkiksi UTF-16), koska monissa tällaisissa merkeissä, esimerkiksi  (0x0100), yksi tavuista on nolla (samaan aikaan UTF- 8-koodaus on vapaa tästä haitasta ).
Molemmilla tavoilla
Kielessä , kuten esimerkiksi Oberon , merkkijono sijoitetaan tietynpituiseen merkkijonoon ja sen loppu on osoitettu tyhjällä merkillä. Oletuksena koko joukko on täytetty nollamerkeillä. Tämän menetelmän avulla voit yhdistää monia molempien lähestymistapojen etuja ja välttää useimmat niiden haitat.
Luettelonäkymä
Kielet Erlang [3] , Haskell [4] , Prolog [5] käyttävät merkkijonotyypin merkkiluetteloa . Tämä menetelmä tekee kielestä "teoreettisesti elegantimman" kunnioittamalla tyyppijärjestelmän ortogonaalisuutta , mutta tuo mukanaan merkittävän suoritusrangaistuksen.
Toteutus ohjelmointikielillä
- Ensimmäisillä ohjelmointikielillä ei ollut merkkijonotyyppiä ollenkaan; ohjelmoijan täytyi rakentaa toimintoja työskennelläkseen jonkin tyyppisten merkkijonojen kanssa.
- C käyttää nollapääteisiä merkkijonoja ohjelmoijan täydellä manuaalisella ohjauksella.
- Normaalissa Pascalissa merkkijono näyttää 256 tavun taulukolta; ensimmäinen tavu tallensi merkkijonon pituuden, loput sen rungon. Näin ollen merkkijonon pituus ei saa ylittää 255 merkkiä. Borland Pascal 7.0 esitteli myös "a la C " -linjat, ilmeisesti johtuen siitä, että Windows sisällytettiin tuettujen alustojen joukkoon .
- Object Pascalissa ja C++ STL :ssä merkkijono on "musta laatikko", jossa muistin varaus/purku tapahtuu automaattisesti - ilman ohjelmoijan osallistumista . Kun merkkijono luodaan, muisti varataan automaattisesti; heti kun merkkijonoon ei ole enää viittausta, muisti palautetaan järjestelmään. Tämän menetelmän etuna on, että ohjelmoijan ei tarvitse ajatella merkkijonojen toimintaa. Toisaalta ohjelmoija ei hallitse riittävästi ohjelman toimintaa nopeuskriittisillä alueilla; on myös vaikeaa välittää tällaisia merkkijonoja parametreina DLL :lle . Lisäksi Object Pascal varmistaa automaattisesti, että merkkijonon lopussa on merkki, jonka koodi on 0. Jos funktio vaatii syötteenä nollapääteisen merkkijonon , sinun tarvitsee vain kirjoittaa tai (Pascalille), (Builderille /STL) muuntaaksesi.PAnsiChar(строковая_переменная)PWideChar(строковая_переменная)переменная.c_str()
- C# : ssa ja muissa roskapostikielissä merkkijono on muuttumaton objekti; jos merkkijonoa on muokattava, luodaan toinen objekti. Tämä menetelmä on hidas ja tuhlaa paljon väliaikaista muistia, mutta sopii hyvin roskien keräämiseen. Tämän menetelmän etuna on, että tehtävä on nopea ja ilman päällekkäisiä rivejä. Merkkijonojen rakentamisessa on myös jonkin verran manuaalista ohjausta ( Javassa esimerkiksi luokkien kautta StringBuffer и StringBuilder) - tämän avulla voit vähentää muistin varausten ja julkaisujen määrää ja vastaavasti lisätä nopeutta.
- Joillakin kielillä (esimerkiksi Standard ML ) on lisäksi lisämoduuli, joka tarjoaa entistä suuremman tehokkuuden - "alimerkkijono" (SubString). Sen käyttö mahdollistaa toimintojen suorittamisen merkkijonoille kopioimatta niiden runkoa manipuloimalla alimerkkijonon alun ja lopun indeksejä; fyysistä kopiointia tapahtuu vain, kun alimerkkijonot on muutettava merkkijonoiksi.
Toiminnot
Perusmerkkijonotoiminnot
- merkin saaminen paikkanumeron (indeksin) mukaan - useimmilla kielillä tämä on triviaali operaatio;
- merkkijonojen ketjuttaminen (yhteys).
Johdannaisoperaatiot
Toiminnot käsiteltäessä merkkijonoja
luetteloina
- konvoluutio ;
- kartoitus luettelosta toiseen;
- suodattaa luettelo kriteerien mukaan.
Monimutkaisempia operaatioita
- etsitään pienin supermerkkijono , joka sisältää kaikki määritetyt merkkijonot;
- etsi kahdesta merkkijonojoukosta yhteensopivia sekvenssejä ( plagiointiongelma ) .
Mahdollisia tehtäviä
luonnollisen kielen merkkijonoille
- määritettyjen merkkijonojen läheisyyden vertailu tietyn kriteerin mukaan;
- tekstin kielen määrittäminen ja koodaus merkkien ja tavujen todennäköisyyksien perusteella.
Merkkijonon esitys
Viime aikoihin asti yksi merkki koodattiin aina yhdeksi tavuksi (8 binääribittiä; käytettiin myös koodauksia, joissa oli 7 bittiä merkkiä kohti), mikä mahdollisti 256 (7-bittisellä koodauksella 128) mahdollisen arvon esittämisen. Kuitenkin useiden kielten aakkosten kirjainten täydelliseen esittämiseen (monikieliset asiakirjat, typografiset merkit - useat lainaustyypit , väliviivat , useat välilyönnit ja tekstien kirjoittaminen hieroglyfikielillä - kiina , japani ja korea ) 256 merkkiä ei riitä. Tämän ongelman ratkaisemiseksi on useita tapoja:
- Kielen vaihto ohjauskoodeilla. Menetelmää ei ole standardoitu ja se riistää tekstiltä riippumattomuuden (eli merkkijono ilman ohjauskoodia alussa menettää merkityksensä); käytetty joissakin ZX-Spectrumin ja BK :n varhaisissa venäläistyksissä .
- Kahden tai useamman tavun käyttäminen kunkin merkin edustamiseen ( UTF-16 , UTF-32 ). Tämän menetelmän suurin haittapuoli on yhteensopivuuden menettäminen aikaisempien tekstikirjastojen kanssa, kun merkkijono esitetään ASCIIZ-muodossa. Esimerkiksi merkkijonon loppua ei pitäisi enää pitää tavuna, jonka arvo on 0, vaan kaksi tai neljä peräkkäistä nollatavua, kun taas yksi tavu "0" voi esiintyä merkkijonon keskellä, mikä hämmentää kirjastoa.
- Koodauksen käyttäminen muuttuvan merkkikoon kanssa. Esimerkiksi UTF-8: ssa jotkut merkit esitetään yhdellä tavulla, jotkut kahdella, kolmella tai neljällä. Tämän menetelmän avulla voit säilyttää osittaisen yhteensopivuuden vanhojen kirjastojen kanssa (merkkijonon sisällä ei ole 0 merkkiä, joten 0:ta voidaan käyttää merkkijonon lopun merkkinä), mutta johtaa siihen, että muistissa olevaa merkkiä ei voida osoittaa suoraan sen sijaintinumero merkkijonossa.
Leksinen analyysi
Kaikkien sanamuotojen yhteensopivuuden tarkistamiseksi leksikaalisen (semanttisen) analyysin aikana käytetään merkkien samankaltaisuusmittauksia:
Katso myös
Muistiinpanot
- ↑ Kallein yhden tavun virhe - ACM-jono . Haettu 17. syyskuuta 2016. Arkistoitu alkuperäisestä 19. syyskuuta 2016. (määrätön)
- ↑ Joel on Software - Takaisin perusteisiin . Haettu 17. syyskuuta 2016. Arkistoitu alkuperäisestä 16. syyskuuta 2016. (määrätön)
- ↑ Simon St. Laurent. Esittelyssä Erlang . - O'Reilly Media, Inc., 2013. - S. 62 . - 185 p. - ISBN 978-1-449-33176-4 .
- ↑ Bryan O'Sullivan, Don Stewart, John Goerzen, Real World Haskell. Liite B. Merkit, merkkijonot ja poistumissäännöt Arkistoitu 26. tammikuuta 2012 Wayback Machinessa
- ↑ SWI-Prolog Manual: 5.2.2 Tekstiä edustava teksti: merkkijonot, atomit ja koodiluettelot Arkistoitu 17. heinäkuuta 2014 Wayback Machinessa