Kirjautuminen

Haku

Tehtävät

Kilpailu

Murra koodi!
Lue ja osallistu!
Seuraava vihje 29.1.
Voittajia 1 + yrittäjiä 1

Keskustelu: Koodit: 8th: Nopea sanahaku käyttämällä BK-puuta

jalski [22.12.2021 22:53:13]

#

BK-puun avulla saadaan haettua hyvin nopeasti tietyllä "etäisyydellä" toisistaan olevia sanoja. Alla oleva esimerkkiohjelma antaa suorittaa ristisana tyyppisiä hakuja kuten esimerkiksi: "_h_e_m_"

Eli haetaan saman pituista sanaa, missä alaviivalla merkitty kirjain voi olla mikä tahansa ja varsinainen kirjain pitää sitten löytyä haettavasta sanasta samalta kohtaa. Löydetyt sanat esitetään listassa. Ohjelmalla kestää muutama sekunti käynnistyä, koska ajettavaan tiedostoon on paketoitu mukaan kotuksen sanastosta muodostettu BK-puu tekstimuodossa ja se pitää lukea ja parsia.

Huomasin myös bugin Nuklearin "edit controllin" toiminnassa. Kursori käyttäytyy huonosti useamman tavun UTF-8 merkkiä kirjoittaessa (liikkuu todennäköisesti merkin tavujen lukumäärän eikä merkin verran).

Jerehän voisi vääntää nettiversion aiheesta... ;-)

Ajettavat binaarit Linux ja Windows käyttöjärjestelmille

needs nk/gui


22 font:system font:new "font1" font:atlas! drop


: metric  \ s1 s2 -- n
  true s:dist ;

"words.bk" app:asset >s tree:parse ' metric tree:cmp! constant words

: split-join+offsets?  \  s1 -- s2 a
  a:new swap "_" >r
  repeat
    r@ s:search null? if
      drop
      break
    else
      _swap dup n:1+ >r a:push swap s:len r@ n:> not if
        rdrop
        break
      else
        r>
      then
    then
  again
  r> s:/ "" a:join swap ;

: compare  \  s1 a s2 -- s1 a T
  s:len 3 pick s:len nip 3 pick a:len nip n:+ n:= if
    swap
    ( '_ s:! ) a:each!
    swap
    "_" s:/ "" a:join
    2 pick s:=
  else
    drop
    false
  then ;

: candidates?  \  s -- a
  dup >r split-join+offsets? a:len words r> rot tree:search nip
  ' compare a:filter nip nip ;


a:new constant list-data


with: nk

: getcount \ -- n
  list-data a:len n:1- nip ;

: getitem \ n -- s
  list-data swap a:@ nip ;

: new-win
  {
    name: "main",
    title: "Sanahaku",
    wide: 0.5,
    high: 0.5,
    bg: "white"
  }
  win
  "list" list-new m! ;

: list-item  \ s --
  nk:TEXT_LEFT "black" nk:label-colored ;

: search
  list-data a:clear "word" nk:get candidates? a:+ ;

: main-render
  {
    bg: "white",
    font: "f1",
    flags: [ @WINDOW_NO_SCROLLBAR ],
    word: ""
  }

  begin
    null  { margin: 4, rows: [32, -1], cols: [0.8, 0.2], cgap: 8, rgap: 8 } layout-grid-begin
      0 1 0 1 grid rect>local grid-push
        "word" get 31 EDIT_FIELD PLUGIN_FILTER_DEFAULT edit-string if
          "word" swap set
        else
          drop
        then
      0 1 1 1 grid rect>local grid-push
        "Hae" ' search button-label
      1 1 0 2 grid rect>local grid-push
        "list" TEXT_LEFT get-row-height getcount "list" m@ dup>r list-begin if
          0 1 layout-row-dynamic
            (
              getitem list-item
            ) r@ list-range drop loop
          r@ list-end
        then rdrop
    layout-grid-end
  end ;

: app:main
  new-win ' main-render -1 render-loop ;

Jere Sumell [24.12.2021 05:24:25]

#

Taisit olla juuri sinä, "jalski", joka esitit tuota BK-puuta tuon sanahaku-ongelman yhteydessä aiemminkin, kun oli tuo säie kuvaristikon laadinnan automatisoimisesta, jonka aloitin aiemmin tänä vuonna loppuvuodesta.

Tuo 8th on itselleni kovin vieras kieli, ja tiedä, mahtaako tuo BK-puurakenne tulla tietojenkäsitteltieteen opinnoissa aineopintoihin sisältyvällä "Edistyneemmät tietorakenteet ja algoritmit" -kussilla, vai vasta sitten, jos Gradusta suosirutuu hyvällä menestyksellä, niin jos opiskelee dosentin tai tohtorin tutkinnon sitten ylemmän korkeakoulutkinnon, tuleeko se siellä vasta. Varmaan jossain vaiheessa tulee.

Tuosta BK-puusta on mielestäni ihan mielekäs esitys "geeksforgeeks" -lähteessä

Täällä.

pitäisi ensin syventyä ja ottaa haltuun (takeover) tuo BK-puurakenne, ennen kuin voisi alkaa implementoimaan sitä jollain nettiselaimella toimivien kielien osalta.

Tänään odotan iltaa, kun tämä Ohjelmointiputkan jouluaaton "Murra koodi" -ongelmanasettelu julkaistaan, minkälainen se on, jos aikaa kuluttaisi sen parissa sitten.

Vastaus

Muista lukea kirjoitusohjeet.
Tietoa sivustosta