semanticdave.se

En webbplats under konstruktion

Skoj med rekursion

När man granskar loggar finner man ofta att sidor som visas efter att användaren klickat på framåt- eller bakåtknappen i webbläsaren inte registreras. Det innebär att man som en del av förarbetet måste fylla igen luckor. Detta är till stor del ett rekursivt arbete. Det startar med att man har två sidor som man ska finna en länk emellan, dvs sida a länkar till b eller tvärtom. Om det inte finns en länk kan man undersöka ifall det finns en gemensam sida som bägge länkar till. a och b länkar inte till varandra men bägge länkar till c, därmed blir vägen a → c b.

Men algoritmen måste ju också täcka upp de fall då b inte länkar till c medan a länkar till c som länkar till b, och användaren bakåtklickat sig från b till a via c efter att ha klickat sig från a till c till b.

Vi har redan stött på patrull, men inget som är olösbart. Om det är så att det helt och hållet saknas sida som länkar ihop a och b blir det lite svårare. Då måste vi först titta på alla sidor p som a länkar till. För varje sida p kollar vi om det finns en länk till b, vilket vi vet att det inte finns (i så fall hade vi funnit den tidigare). Så vi kollar varje sida q som p länkar till, och sedan varje sida r som q länkar till tills vi funnit en länk till b. I själva verket finns det ingen sida q eller r, alla representeras av p som är en del av en rekursion.

När vi väl funnit en väg fram till b har vi en lång rad sidor som inte är del av vägen. Vi har samlat på oss alla sidor som a länkar till, och som p länkar till (inkluderat resultatet av rekursionen förstås). Därför måste vi skicka listan med sidor vidare till en funktion som rensar sökvägen. Denna funktion börjar bakifrån och kontrollerar om det finns en länk från näst sista sidan till den sista och tvärtom. Om inte plockas näst sista sidan bort och funktionen anropas på nytt med den nya listan med sidor. Är det så att det finns en länk mellan sidorna anropas funktionen igen med samma lista, men med instruktionen om att de x sista sidorna kan ignoreras.

Slutligen, när vi har fått en väg mellan de båda sidorna, ska vi vända på vägen. Exempel: vi har vägen abcd e a i loggen och vi saknar länk mellan e och a. e tar platsen som firstPage i algoritmen och a platsen som secondPage (det är egentligen vägen a e som vi söker). Vi finner att a inte länkar till e så vi testar om a länkar till sida som länkar till e. Detta stämmer inte heller eftersom a bara länkar till b. Men vi finner att a länkar till b som länkar till c som länkar till d som länkar till e tack vare rekursiva funktionen find_page. Hade vi nu, som på en normal webb är väldigt troligt, haft flera utgående länkar från sidorna hade vi samlat på oss ett antal sidor som är del av vägar som inte leder till e. Dessa måste rensas bort med clean_path.

Vår väg är för enkelhetens skull helt perfekt redan. Den är abcd e. Vägen från e till a blir då den omvända vägen edcba. Värt att notera är att det är mycket möjligt att användaren gått från e till a genom att klicka på ett bokmärke eller genom att skriva in a:s url.

Algoritmen

sessionPages ← secondPage, firstPage
for i = 0, i < sessionPages.count - 1, i++ do
  if sessionPagesi links to sessionPagesi+1 then
    output path sessionPagesi, sessionPagesi+1
  else if sessionPagesi+1 links to page p and p links to sessionPagesi then
    output path sessionPagesi, p, sessionPagesi+1
  else
    c = 0
    pagehit = 0
    foreach page p that sessionPagesi links to do
      pathscp, sessionPagesi
      visitedPagescp, sessionPagesi
      if pagehit == 0 then
        pagehit = find_page(sessionPagesi, p, pagehit, pathsc, c, visitedPagesc)
      endif
      if pagehit == 1 then
        pagehit = 0
      endif
      c++
    endforeach
  endif
endfor

Enkelt så långt, men nu ska vi titta på find_page:

function find_page(to, from, pagehit, path, c, visitedPages)
  if pagehit == 0 then
    visitedPages ← from
    foreach page p that from links to do
      if pagehit == 0 then
        if p not in visitedPages then
          path ← p
        endif
        if p == from then
          pagehit = 1
        if from not in visitedPages then
          path ← from
        endif
          clean_path(path, ignores = 0, c)
        else if p == to then
          pagehit = 1
        if to not in visitedPages then
          path ← to
        endif
          clean_path(path, ignores = 0, c)
        endif
        linksFromTo ← p
      endif
    end foreach
    if pagehit == 0 then
      foreach i in linksFromTo
        if i not in visitedPages then
          pagehit = find_page(to, i, pagehit, path, c, visitedPages)
        endif
      endforeach
    endif
  endif
  return pagehit
end function

function clean_path(path, ignores, c)
  cleanPath = chech_path(path)
  if cleanPath == false then
    pathCopy = path
    for i = 1, i <= ignores, i++ do
remove last item in pathCopy
endfor
if pathCopy.count >= 2 then
lastItem = pathCopy.last
remove last item in pathCopy
secondLastItem = pathCopy.last
remove last item in pathCopy
if !(lastItem links to secondLastItem or
secondLastItem
links to lastItem) then
remove secondLastItem from path
else
ignores++
endif
clean_path(path, ignores, c)
endif
else
output path
endif
end function

function check_path(path)
cleanPath = true
for i = 0, i < path.count - 1, i++ do
first = pathi
second = pathi+1
if !(first links to second or second links to first) then
cleanPath = false
endif
return cleanPath
end function

SemanticDave @ 2010-08-26 14:01:35 (uppdaterad 2010-11-30 18:57:50) » Permalänk

algoritm luckfyllning preprocessing data mining logganalys rekursion

Stöd för specialtecken!

Den här algoritmen har jag roat mig en del med under våren och sommaren:

C1 ← init-pass(T)
F1 ← {f | fC1,f.count/nminsup};
for (k = 2; Fk-1 ≠ ∅; k++) do
Ck ← candidate-gen(Fk-1);
for each transaction tT do
for each candidate cCk do
if c is contained in t then
c.count++;
endfor
endfor
Fk ← {cCk | c.count/nminsup}
endfor
return F ← ∪k Fk;

Vilken algoritm rör det sig om? En hint (och en nödvändig referens på köpet) är att den är hämtad från en bok med ISBN 978-3-540-37881-5.

När man gör sådana här saker är det förstås bra om man kan skilja på em och i eftersom en kursivering i det här fallet inte handlar om en emfasifiering utan snarare om en visuell framhävning varför i skulle fungera bättre, men man kan ju inte få allt.

SemanticDave @ 2010-08-08 01:19:19 (uppdaterad 2010-08-27 11:22:42) » Permalänk

semantisk html algoritm specialtecken

SIDA 1