Archive for november, 2003

Mer bloggsökning

Posted in Frisim on november 27th, 2003 by Clas – Kommentering avstängd

Jag har adderat fler bloggar till dem som indexeras till alfa-versionen av Frisim/blogs. Fortfarande uppdaterar inte databasen automatiskt. Det beror på att jag har inte orkat installera Java JDK1.4 som krävs för sök-roboten. (Paketet Xerces finns i den, vilket paketet Informa kräver.)

Lite cool att det går att göra ”populäritetssökningar” som:
http://www.frisim.se/frisim/servlet/BlogSearch?searchString=mymarkup+-url%3Amymarkup&submit.x=0&submit.y=0
där svaren är bloggar som skriver eller länkar till blloggen ”mymarkup” (www.mymarkup.net) men inte har ”mymarkup” i URL:en.

En alfa-version av kommande blogsökmotorn

Posted in Frisim on november 25th, 2003 by Clas – Kommentering avstängd

Ah, nu har jag knåpat ihop ett webbgränssnitt mot blog-databasen. Tyvärr har jag inte orkat flytta programmet som samlar in data, så jag kan fortfarande bara visa upp en version där databasen över indexerade bloggar är liten och konstant, vilket innebär att den alltså inte uppdaterar sig automatiskt med nya bloggar ännu. Antagligen finns också ett antal andra problem som jag inte har upptäckt ännu.

Men i alla fall, prova gärna! Den finns på (den tillfälliga) adressen:
http://www.frisim.se/frisim/servlet/BlogSearch.
En sökning på ordet Google, sorterad i tidsordning, görs med:
http://www.frisim.se/frisim/servlet/BlogSearch?searchString=google&s=1.

En sökning i MyMarkup.net på ord som börja med ”blog” görs med: http://www.frisim.se/frisim/servlet/BlogSearch?searchString=blognamn%3Amymarkup+blog*&p=0&s=1

Funkar det? Jag är tacksam om du berättar vad du tycker =)

Just nu visas bara de 130 första teckning i själv bloggen. Vill du läsa hela bloggen så får du klicka på länken och läsa på blogg-sidan. Om inlägget är kostare än 130 tecken står istället ”Inlägget saknar beskrivning”. Det känns lite surt att ta och visa upp hela texten, speciellt för dem som har reklam på sin blog. Men de kanske inte har en RSS med allt innehåll med i? Jag funderar vidare på detta. Det är inget problem att ändra så att hela ”bloggen” (HTML-formaterad eller inte) syns direkt bland sökresultaten.

Lite mer blogsökmotorfunderingar

Posted in Frisim on november 23rd, 2003 by Clas – Kommentering avstängd

Efter att ha bränt några timmar på att bygga mig en plattform för RSS/XML/RDF-tolkning så börjar jag se problemen. Speciellt finns det ett problem med <content:encode>-data, som finns för att folk ska kunna lägga in formaterade, kompletta, inlägg i sin RSS-feed. Just denna ”encoding” är det inte mycket nytta med när man har tänkt att indexera texten. Det ställer mest till problem med svenska tecken och annat HTML-skräp som jag inte vill ha. RSS borde ha fokus på text och länkar (möjligen) men inte formatering av data. Borde man inte köra stylesheets för det!? Hur som helst så måste man alltså ”dekoda” kodade data för att kunna indexera dem.

Det som finns klart nu är i alla fall ett litet(?) program som laddar RSS-feeds från ett antal svenska bloggar, och indexerar nya inlägg. För tillfället finns bara ett kommandorads-gränssnitt, men kanske kan de bli ett webbgränssnitt om någon vecka eller så. Ännu finns ingen koppling mot t.ex. SweBlogs eller Weblogs.se, men det bör vara enkelt om man kan hitta är lämplig feed från någon av dem. Jag kommer dock bara att indexera svensk text!

Funderingar kring en blog-sökmotor

Posted in Frisim on november 23rd, 2003 by Clas – Kommentering avstängd

Jag har lite smått börjat titta på hur man skulle kunna bygga en sökmotor för bloggar. Det som avskräcker en aning är den RSS/XML/RDF-djungel för publicering av data som finns där ute. När det gäller nyheter, som jag har viss erfarenhet av sedan tidigare är det naturligtvis ännu värre, men förhoppningen var att det borde vara enklare med dessa syndikseringsformat, då ju källan använder någon standard för publiceringen och man borde slippa använda en HTML-parser för att hitta det man vill åt.

I alla fall så är en av grundstenarna i en blog-sökmotor en parser för dessa RSS/XML/RDF-filer. Givet att man kan läsa dessa, eller i alla fall de flesta av dessa, så borde det inte vara så lurigt att göra indexering och sökformulär. Mycket av koden för indexering och sökformulär kan återanvändas från Frisim.

Eftersom jag inte är så sugen på att skriva en egen parser för blog-syndikerade data så låg det nära till hands att titta vad som finns på nätet. Lite googlande resulterade i inskiten att det finns massor med mer eller mindre färdiga små projekt för detta. Problemet är snarast att orka prova from en kod som fungerar tillräckligt bra. (Den bör provas på ett gäng olika format och sånt tar rätt mycket tid.) Dessutom vore det fint att hitta ett projekt som fortfarande utvecklas och byggs på med fler format allt eftersom de blir populära. Från början hade jag som mål att hitta någon kod som fungerar bra och är hyggligt strukturerad, och eventuellt själv skriva om den i Java. Sån tur var så är alternativen så många att det verkar möjligt att hitta även Java-baserad kod.

Jag fastnade, utan allt för mycket provande, för Informa API:t. Informa är mycket mer än en parser, det är en hel miljö för hantering av t.ex. blog-data. Som jag uppfattar koden skulle det gå relativt smärtfritt att bygga en egen NewsMonster på den. Informa använder sig av Xerces SAX parser. Jag kommer dock ”bara” att använda själva RSS-parsern. Vid en första anblick fungerar den grymt bra. Informa-parsern hanterar dock bara relativt korrekt skrivna RSS/XML/RDF-filer, men förhoppningsvis så får det bara en fostrande effekt, och inte effekten att man missar en massa bra bloggar.

Det återstår dock lite funderande kring hur t.ex. länkar och bilder i RSS-filerna skall hanteras. Lämpligen markeras länkar upp, på något sätt, så att det blir möjligt att se kopplingar mellan blog-inlägg. Bilder kanske man helt enkelt kan kasta utan att det märks. Övrig formtering som verkar finnas i vissa RSS-filer (i ”content”-blocken) kanske också kan kastas utan att det spelar någon roll.

Kanske kan de bli en beta-version av en blog-sökmotor till jul, eller nåt…

Blogsökmotor

Posted in Frisim on november 18th, 2003 by Clas – Kommentering avstängd

På sajten search.toblogornot.com har Mattias börjat bygga en sökmotor för webbloggar. Den ser ut att fungera bra tycker jag, men det är fortfarande ganska få inlägg att söka bland så det är ännu lite för tidigt för att kunna göra en bra gissning på hur sökningarna görs. Söksajten kör på en Windows-burk hos Bonet med Apache och mod_php, så det troliga är väl att det är FULLTEXT-sökningar i en MySQL-databas som används, men kanske har han hittat något bättre!?

Jag önskar att jag en vacker dag kan bygga något liknande och erbjuda lite konkurrens =) Jag skulle dock vilja ha en push-baserad version så att man slipper ladda och ”parsa” så mycket data. Jag har jämt att göra med våra nyhetsartiklar. Kanske skulle man kunna få ”push”-singaler från weblogs.se om när det finns en blog som har uppdaterat? Finns det kanske en RSS med de senaste uppdaterade bloggarna att hämta (ofta) från Weblogs.se?

Jag föreslog snubben bakom Gooliat att vi skulle samarbeta kring bygget av en webblogsökmotor, men vår email-kommunikationen går lite för långsamt för att det ska fungera bra.

Som jag gissade i ett tidigare inlägg, kör Gooliat mot en SQL-databas med FULLTEXT-indexerade artiklar. Det är ett mycket smidigt alternativ, men är rätt kapacitetskrävande (alternativt långsamt) när datamängden är stor. Gooliat säger sig ha 250 000 artiklar i sitt index, och det går rätt långsamt, när det fungerar, att göra en sökning på ett vanligt ord, tex ”och”. Och det är fortfarande något konstigt med Gooliat: Det står att de har 250000 artiklar men en sökning på ”finns” returnerar knappt 7000 stycken. Frisim har nu 45000 artiklar [tack vare att vi just tappade 2 veckors artiklar i "hårddiskkraschen" i söndags] men returnerar fler än 10000 artiklar med ”finns” i.

Nyhetssökningsideer

Posted in Sökmotorer on november 18th, 2003 by Clas – Kommentering avstängd

Slashdot har en rubrik om en liten nyhetssajt som bara visar små bilder från nyhetsartiklar. Klickar man på bilden kommer man till artikeln. Rätt trevlig ide. Ännu trevligare är det att läsa alla kommentarer och länktips från Slashdot-läsare. Det visar sig finnas rätt många liknande sajter, vissa använder Google News för att identifiera nyheterna, som BigFrog, andra kopierar helt enkelt Google News: Textz.

Mera intressant är NewsQuake som placerar nyheter på en världskarta. Kul idé, kanske kan man göra på samma sätt med svenska nyheter på en sverigekarta!

Också intressant är Marketing Wonk:s nyhet om att MSN startar en konkurrent till Google News. En beta-version (som vanligt i nyhetssökbranchen?) finns på uk.newsbot.msn.com/. Den är, tycker jag, snyggare än Google:s, framförallt är bilderna något tydligare (och köps av Reuters?) men i övrigt är upplägget detsamma. Tyvärr finns ingen info om källor, eller hur nyheterna hittas och placeras på sidan.

Google Mathematics-seminarium

Posted in Sökmotorer on november 17th, 2003 by Clas – Kommentering avstängd

Idag var jag på detta seminarium som gavs på ”Numme”-avdelningen på matematiska institutionen på Linköpings universitet. Seminariet hölls av Lars Eldén som är tidigare instutitionskollega till mig under min doktorandtid på matematiska instutitionen. (På Lars hemsida finns OH-bilderna från presentationen!)

Seminariet handlade om rangordning av sökresultat i en sökmotor, och speciellt hur Google rangordnar sina sökresultat. En sökmotor fungerar (vanligen) så att man skriver in ett eller flera sökord (säg ett för enkelhets skull) och tar fram alla dokument som innehåller det ordet. Detta räcker dock inte eftersom ingen brukar orka titta igenom alla resultaten för att se om de ”duger”. Alltså måste alla webbsidor som innehåller ditt sökord rangordnas, och frågan är hur man gör detta för att det skall uppfattas som en bra rangordning. I fallet Google används den i Googlekretser välbekanta, men likväl mystiska, PageRank-sorteringen.

Det var om PageRank, och en algebraisk tolkning av den, som seminariet handlade.

För varje indexerad webbsida i indexet vill vi beräkna ett ”PageRank”, ett tal mellan noll och ett. Ju högre PageRank desto intressantare sida. Det räcker alltså inte att titta på de sidor som innehåller det ord du just sökt på, utan PageRank vill man(?) veta för alla sidorna innan sökningen startar. (Det nämndes inte på seminariet, men RageRank är lite av nyckeln till varför Google är så snabb när det gäller att svara på en sökning. Den vet helt enkelt var den skall börja leta då den redan har alla sidor i PageRank-ordning, och sidor med högre PageRank skall visas högre upp bland resultaten. Det innebär t.ex. att man inte behöver titta igenom hela indexet för att hitta de 10 första sökresultaten. Detta kan observeras tydligt på Google: Prova att ta fram det 801:a sökresultatet, på den 80:de resultatsidan och notera att det tar betydligt längre tid än att ta fram den den första resultatsidan.)

Det är inte någon speciellt avancerad matematik/algebra som behövs för att beskriva hur PageRank fungerar.

Vad som kan kallas för ”PageRank-problemet” är att finna ett PageRank-tal, r, för alla n:st webbsidor så att




Här är r_i RageRank för sida i, I_i är antalet inlänkar till sida i och N_j är antalet utlänkar från sida j. Detta är ett rekursivt samband.

Frågor som en matematiker, eller numeriker, nu ställer sig är om det finns en lösning till detta. Om det gör det, finns det bara en lösning? (Är lösningen entydig?). Kan man svara ja på dessa (och det kan man i detta fall) så frågar man sig hur man beräknar r_i för alla i.

Det som gör det hela svårt är att n är stort, dvs webbsidorna i indexet är väldigt många. Google har c:a 3 miljarder sidor i sitt index, och uppdateringen har (åtminstone fram till nu) skett ungefär var fjärde vecka. Det innebär att det absolut inte får ta mer än så lång tid att beräkna detta, för att rangordna sidorna.

Det, för en numeriker, som är speciellt intressant i detta är att ”PageRank-problemet” ovan, kan tolkas i matrisoperationer som beräkningen en egenvektor för en länk-struktur-matris (Q i seminarieanteckningarna). Q-matrisen är en matris som innehåller nollor, förutom på vissa element som indikerar att det är möjligt att ta sig (via ett klick!) från en sida till en annan. Denna koppling, mellan PageRank-problemet och egenvektorberäkningen, kan dock göras först efter lite manipulering av Q-matrisen. Denna Q-matris kan tolkas i termer av en ”slumpvandring”, eller ”slumpsurfare”, i den mening att elementen i Q kan tolkas som sannolikheten att en ”slumpsurfare” förflyttar sig från en viss sida till en annan (en ”transition probability”). Sidor med fler länkar till sig, och speciellt länkar från sidor med högt r_i, får en högre sannolikhet att besökas av denne slumpsurfare.

Den manipulering som behövs av Q-matrisen innan vidare behandling kan göras kan, i princip, tolkas som att vi vill förhindra ”slumpsurfaren” från att fastna på webbsidor som inte har några utlänkar och förhinda han/hon att fastna på en liten ”ö” av webbsidor. Denna manipulering innebär i matematiska termer att en rang-1 uppdatering av Q-matrisen görs så att ingen kolumn i Q innehåller bara nollor. Denna rang-1 uppdatering kan i sin tur tolkas i termer av ”slumpsurfaren” som att denne hoppar iväg till en slumpmässig sida med viss sannolikhet. Man kan se det som att kan lägger in osynliga länkar på alla webbsidor till alla andra webbsidor. Hur troligt det är att ett sådant ”hopp” sker beror på en parameter alfa som ingår i rang-1 uppdateringen.

Storleken på alfa påverkar hur ”enkelt” PageRank-problemet är att lösa. Konvergenshastigheten (och därmed lösningstiden) hos Potensmetoden som lämpligen används för problemet påverkas direkt av valet av denna parameter. Potensmetoden i sig är ”gammal skåpmat” men är i detta fall, på grund av att antalet webbsidor som skall rangordnas är mycket stort, trots allt intressant eftersom alternativ just nu saknas.

Seminariet var intressant! För den som är intresserad av att beräkna (något som liknar) PageRank på ett eget litet index bör ta en titt på bilderna från seminariet.

Återställning av server

Posted in Frisim on november 17th, 2003 by Clas – Kommentering avstängd

Hmm, nu har jag fått tillgång till min senaste ”backup” som är bara några timmar före kraschen. Nu är de flesta filer tillbakaflyttade, och det mesta borde se ut som tidigare… Det som kvarstår är att fixa databasen med användare. Vet inte om jag vågar rsync:a in den från backupen, eller om jag skall göra det manuellt. Jag tror att jag gör det blir manuellt, det är nog inte så mycket jobb och det får inte gå fel. Klart till kvällen!

frisim.se-server back up

Posted in Frisim on november 17th, 2003 by Clas – Kommentering avstängd

Wow, nu är vi vår server uppe igen =) Dock är det mycket riktigt så att två veckors ”tweakningar” och prenumerationsinställningar ”försvunnit” i diskkrashen. Fan, det låter bra med backups, men det är ju surt att de aldrig fungerar. Hmm, förhoppningsvis klarar jag av att fixa allt ”back to normal ” på ett par tre timmar … i kväll…

Vill ni ha ett hett tips på ett ställe att inte köra server på så kan jag bistå med ett ;-)

Snart uppe igen, kanske….

Posted in Frisim, Osorterad on november 17th, 2003 by Clas – Kommentering avstängd

Wow, nu skall servern vara uppe igen. Nu skall vi bara se vad det är som fungerar…

Framåt eftermiddagen kanske det är möjligt att få igång detta igen. *blä*