Hoe zou je Lucene.NET gebruiken om zoeken te helpen implementeren op een site als Stack Overflow?

Ik heb een soortgelijke vraag gesteld op Meta Stack Overflow, maar dat gaat specifiek over het al dan niet Lucene.NETwordt gebruikt op Stack Overflow.

Het doel van de vraag hier is meer een hypotetische, wat betreft de benaderingen die men zou maken als ze Lucene.NET zouden gebruiken als basis voor in-site zoeken en andere factoren in een site zoalsem>Stack Overflow [SO].

Volgens het bericht op de Stack Overflow-blog met de titel “SQL 2008 Full-Text Search Problems” er was een sterkeindicatie dat Lucene.NET op een gegeven moment werd overwogen, maar het lijkt erop dat dit zeker niet het geval is, zoals blijkt uit de opmerking van Geoff Dalgasop 19 februari 2010:

Lucene.NET wordt niet gebruikt voor Stack
Overloop – we gebruiken SQL Server
Indexering van volledige tekst. Zoeken is een gebied
waar we doorgaan met het maken van minor
aanpassingen.

Dus mijn vraag is, hoe zou je Lucene.NET gebruiken op een site die dezelfde semantiek heeft als Stack Overflow?

Hier is wat achtergrondinformatie en wat ik tot nu toe heb gedaan/overdacht (ja, ik heb het meeste hiervan geïmplementeerd en zoeken is het laatste aspect dat ik moet voltooien):

Technologieën:

En natuurlijk de ster van de show, Lucene.NET.

Het is ook de bedoeling om zo snel mogelijk over te gaan naar .NET/C# 4.0. Hoewel ik niet denk dat het een game-changer is, moet het worden opgemerkt.

Alvorens in te gaan op aspecten van Lucene.NET, is het belangrijk om te wijzen op de SQL Server 2008-aspecten ervan, evenals de betrokken modellen.

Modellen

Dit systeem heeft meer dan één primair modeltype in vergelijking met Stack Overflow. Enkele voorbeelden van deze modellen zijn:

  • Vragen: dit zijn vragen die mensen kunnen stellen. Mensen kunnen vragen beantwoorden, net als op Stack Overflow.
  • Opmerkingen: dit zijn projecties in één richting, dus in plaats van een vraag, maak je een statement over de inhoud. Mensen kunnen hier geen reacties op plaatsen.
  • Evenementen: dit zijn gegevens over een realtime evenement. Het heeft locatie-informatie, datum/tijd-informatie.

Het belangrijkste om op te merken over deze modellen:

  • Ze hebben allemaal een eigenschap Name/Title (tekst) en een eigenschap Body (HTML) (de indelingen zijn niet relevant, omdat de inhoud op de juiste manier wordt geparseerd voor analyse).
  • Elke instantie van een model heeft een unieke URL op de site

Dan zijn er de dingen die Stack Overflow biedt, die IMO, decorateurs zijn voor de modellen. Deze decorateurs kunnen verschillende kardinaliteiten hebben, ofwel één-op-één of één-op-veel:

  • Stemmen: ingetoetst op de gebruiker
  • Antwoorden: Optioneel, zie als voorbeeld de casus Notes hierboven
  • Favorieten: staat het model vermeld als favoriet van een gebruiker?
  • Opmerkingen: (optioneel)
  • Tag-associaties: tags staan ​​in een aparte tabel, zodat de tag niet voor elk model wordt gerepliceerd. Er is een koppeling tussen het model en de tabel met tag-associaties en vervolgens van de tabel met tag-associaties naar de tabel met tags.

En er zijn ondersteunende overeenkomsten die op zichzelf een-op-een-decorateur zijn van de modellen die op dezelfde manier aan hen zijn gekoppeld (meestal door een model-ID-type en de model-ID):

  • Aantal stemmen: totaal aantal positieve, negatieve stemmen, Wilson Score-interval(dit is belangrijk, het gaat het betrouwbaarheidsniveau bepalen op basis van stemmen voor een inzending, voor het grootste deel uitgaand van de ondergrens van het Wilson-interval).

Antwoorden (antwoorden) zijn modellen die de meeste decorateurs hebben die de meeste modellen hebben, ze hebben alleen geen titel of URL, en of een model een antwoord heeft of niet, is optioneel. Als antwoorden zijn toegestaan, is het natuurlijk een een-op-veel-relatie.

SQL Server 2008

De tabellen volgen vrijwel de lay-out van de bovenstaande modellen, met aparte tabellen voor de decorateurs, evenals enkele ondersteunende tabellen en weergaven, opgeslagen procedures, enz.

Opgemerkt moet worden dat de beslissing om geen full-text zoeken te gebruiken voornamelijk gebaseerd is op het feit dat scores zoals Lucene.NET niet worden genormaliseerd. Ik sta open voor suggesties voor het gebruik van op tekst gebaseerde zoekopdrachten, maar ik zal zoekopdrachten moeten uitvoeren in meerdere modeltypen, dus houd er rekening mee dat ik de score op de een of andere maniermoet normaliseren.

Lucene.NET

Dit is waar het grote vraagteken staat. Dit zijn mijn gedachten tot nu toe over de Stack Overflow-functionaliteit en hoe en wat ik al heb gedaan.

Indexeren

Vragen/modellen

Ik ben van mening dat elk model een eigen index zou moeten hebben met een unieke id om deze snel op te zoeken op basis van een Term-instantie van die id (geïndexeerd, niet geanalyseerd).

Op dit gebied heb ik overwogen om Lucene.NET elke vraag/model en elk antwoord afzonderlijk te laten analyseren. Dus als er één vraag en vijf antwoorden waren, zouden de vraag en elk van de antwoorden afzonderlijk als één eenheid worden geïndexeerd.

Het idee hier is dat de relevantiescore die Lucene.NET retourneert, gemakkelijker te vergelijken zou zijn tussen modellen die op verschillende manieren projecteren (bijvoorbeeld iets zonder antwoorden).

Bijvoorbeeld: een vraag bepaalt het onderwerp en het antwoord gaat dieper in op het onderwerp.

Voor een notitie waarop geen antwoorden staan, behandelt het de kwestie van het presenteren van het onderwerp en het uitwerken ervan.

Ik denk dat dit zal helpen om de relevantiescores relevanter voor elkaar te maken.

Tags

Aanvankelijk dacht ik dat deze in een aparte index moesten worden bewaard met meerdere velden die de id’s van de documenten in de juiste modelindex hebben. Of, als dat te groot is, is er een index met alleen de tags en een andere index die de relatie tussen de tagsindex en de vragen waarop ze worden toegepast in stand houdt. Op deze manier, wanneer u op een tag klikt (of de URL-structuur gebruikt), is het gemakkelijk om op een progressieve manier te zien dat u alleen hoeft te “kopen in” als u erin slaagt:

  • Als de tag bestaat
  • Aan welke vragen de tags zijn gekoppeld
  • De vragen zelf

In de praktijk is het echter uiterst eenvoudigmet SQL Server 2008 om alle items te doorzoeken op basis van tags (zoals klikken op een tag in Stack Overflow). vereist eenvoudig een zoekopdracht zoals:

select
     m.Name, m.Body
from
    Models as m
        left outer join TagAssociations as ta on
            ta.ModelTypeId = <fixed model type id> and
            ta.ModelId = m.Id
        left outer join Tags as t on t.Id = ta.TagId
where
    t.Name = <tag>

En aangezien bepaalde eigenschappen door alle modellen worden gedeeld, is het eenvoudig genoeg om een ​​UNIONuit te voeren tussen verschillende modeltypes/tabellen en een consistente reeks resultaten te produceren.

Dit zou analoog zijn aan een TermQueryin Lucene.NET (ik verwijs naar de Java-documentatie omdat het veelomvattend is, en Lucene.NET is bedoeld als een regel voor regel vertaling van Lucene, dus alle documentatie is hetzelfde).

Het probleem dat zich voordoet bij het gebruik van Lucene.NET is de sorteervolgorde. De relevantiescore voor een TermQuery als het gaat om tags is niet relevant. Het is 1 of 0 (het heeft het of het heeft het niet).

Op dit punt komt de betrouwbaarheidsscore (Wilson-score-interval) in het spel om de resultaten te ordenen.

Deze score zou kunnen worden opgeslagen in Lucene.NET, maar om de resultaten op dit veld te sorteren, zou het afhangen van de waarden die worden opgeslagen in de veldcache, iets wat ik echt, echt wil vermijden. Voor een groot aantal documenten kan de veldcache erg groot worden (de Wilson-score is een dubbele, en je zou één dubbele nodig hebben voor elk document, dat kan één grote array zijn).

Aangezien ik de SQL-instructie in volgorde kan veranderen op basis van het Wilson-score-interval als volgt:

select
     m.Name, m.Body
from
    Models as m
        left outer join TagAssociations as ta on
            ta.ModelTypeId = <fixed model type id> and
            ta.ModelId = m.Id
        left outer join Tags as t on t.Id = ta.TagId
        left outer join VoteTallyStatistics as s on
            s.ModelTypeId = ta.ModelTypeId and
            s.ModelId = ta.ModelId
where
    t.Name = <tag>
order by
    --- Use Id to break ties.
    s.WilsonIntervalLowerBound desc, m.Id

Het lijkt een gemakkelijke keuze om dit te gebruiken om de Stack Overflow-functionaliteit “alle items getagd met <tag>” te laten werken.

Antwoorden

Oorspronkelijk dacht ik dat dit in een aparte index stond, met een sleutel terug naar de index Vragen.

Ik denk dat er een combinatie van elk model en elk antwoord (als die er is) moet zijn, zodat de relevantiescores tussen verschillende modellen meer “gelijk” zijn in vergelijking met elkaar.

Dit zou natuurlijk de index doen opzwellen. Ik voel me daar nu een beetje comfortabel bij.

Of, is er een manier om bijvoorbeeld de modellen en antwoorden op te slaan als afzonderlijke documenten in Lucene.NET en vervolgens beide te nemen en de relevantiescore te krijgen voor een zoekopdracht waarbij beide documenten als één? Zo ja, dan zou dit ideaalzijn.

Het is natuurlijk de vraag welke velden zouden worden opgeslagen, geïndexeerd, geanalyseerd (alle bewerkingen kunnen afzonderlijke bewerkingen zijn of worden gecombineerd)? Hoeveel zou één indexeren?

Hoe zit het met het gebruik van speciale stemmers/porters voor spelfouten (metafoon gebruiken) en synoniemen (er is terminologie in de community die ik zal bedienen die zijn eigen jargon/terminologie heeft voor bepaalde dingen die meerdere representaties heeft)?

Boost

Dit heeft natuurlijk met indexeren te maken, maar ik denk dat het een eigen sectie verdient.

Bent u versterktvelden en/of documenten? Zo ja, hoe stimuleer je ze? Is de boost constant voor bepaalde velden? Of wordt het opnieuw berekend voor velden waar stemmen/bekijken/favoriete/externe gegevens van toepassing zijn.

Krijgt de titel in het document bijvoorbeeld een boost over het lichaam? Zo ja, welke stimulerende factoren werken volgens u goed? Hoe zit het met tags?

Het denken hier is hetzelfde als in de trant van Stack Overflow. Termen in het document hebben relevantie, maar als een document is getagd met de term of in de titel staat, moet het worden versterkt.

Shashikant Koresuggereert een documentstructuur als deze:

  • Titel
  • Vraag
  • Geaccepteerd antwoord (of hoog gestemd antwoord als er geen geaccepteerd antwoord is)
  • Alle antwoorden gecombineerd

En dan boost gebruiken, maar niet op basis van de onbewerkte stemwaarde. Ik geloof dat ik dat heb afgedekt met het Wilson Score-interval.

De vraag is of de boost op het hele document moet worden toegepast? Ik neig naar nee op deze, omdat het zou betekenen dat ik het document opnieuw zou moeten indexeren telkens wanneer een gebruiker op het model stemde.

Zoeken naar items getagd

Oorspronkelijk dacht ik dat bij het zoeken naar een tag (door specifiek op een tag te klikken of door de URL-structuur te gebruiken om getagde inhoud op te zoeken), dat een eenvoudige TermQuery is tegen de tagindex voor de tag en vervolgens in de associatie-index (indien nodig ) en dan terug naar de vragen, Lucene.NET handelt dit heel snel af.

Gezien de bovenstaande opmerkingen over hoe gemakkelijk het is om dit in SQL Server te doen, heb ik echter voor die route gekozen als het gaat om het zoeken naar getagde items.

Algemeen zoeken

Dus nu is de meest openstaande vraag wanneer u een algemene zoekactie op een woordgroep of term uitvoert op inhoud, wat en hoe integreert u andere informatie (zoals stemmen) om de resultaten in de juiste volgorde te bepalen? Als u deze zoekopdracht bijvoorbeeld uitvoert op ASP.NET MVC op Stack Overflow, zijn dit de resultaten voor de top vijf resultaten (bij gebruik van het tabblad relevantie):

   q votes answers accepted answer votes asp.net highlights mvc highlights
    ------- ------- --------------------- ------------------ --------------
         21      26                    51                  2              2
         58      23                    70                  2              5
         29      24                    40                  3              4
         37      15                    25                  1              2
         59      23                    47                  2              2

Houd er rekening mee dat de hoogtepunten alleen in de titel en samenvatting op de resultatenpagina staan ​​en slechts kleine indicatoren zijn voor wat de werkelijke termfrequentie is in het document, de titel, de tag, het antwoord (hoe ze ook worden toegepast, wat een ander goed is vraag).

Hoe wordt dit allemaal bij elkaar gebracht?

Op dit moment weet ik dat Lucene.NET een genormaliseerde relevantiescore zal retourneren, en de stemgegevens zullen me een Wilson-score-interval geven dat ik kan gebruiken om de betrouwbaarheidsscore te bepalen.

Hoe moet ik kijken naar het combineren van twee scores om de sorteervolgorde van de resultatenset aan te geven op basis van relevantie en vertrouwen?

Het is mij duidelijk dat er eenrelatie tussen de twee zou moeten zijn, maar wat die relatie zou moeten zijn ontgaat me op dit moment. Ik weet dat ik het in de loop van de tijd moet verfijnen, maar ik ben echt de weg kwijt op dit onderdeel.

Mijn eerste gedachten zijn dat als de relevantiescore tussen 0 en 1 ligt en de betrouwbaarheidsscore tussen 0 en 1, dan zou ik zoiets als dit kunnen doen:

1 / ((e ^ cs) * (e ^ rs))

Op deze manier krijgt men een genormaliseerde waarde die 0 benadert, hoe relevanter en zekerder het resultaat is, en daarop kan worden gesorteerd.

Het belangrijkste probleem daarbij is dat als boosting wordt uitgevoerd op het tag- en/of titelveld, de relevantiescore buiten de grenzen van 0 tot 1 ligt (de bovenkant wordt dan onbegrensd en ik weet niet hoe ik daar mee omgaan).

Ook geloof ik dat ik de vertrouwensscore zal moeten aanpassen om rekening te houden met stemmen die volledig negatief zijn. Aangezien volledig negatieve stemmen resulteren in een Wilson-score-interval met een ondergrens van 0, heeft iets met -500 stemmen dezelfde betrouwbaarheidsscore als iets met -1 stem of 0 stemmen.

Gelukkig daalt de bovengrens van 1 naar 0 naarmate het aantal negatieve stemmen stijgt. Ik zou de betrouwbaarheidsscore kunnen wijzigen in een bereik van -1 tot 1, zoals:

confidence score = votetally < 0 ? 
    -(1 - wilson score interval upper bound) :
    wilson score interval lower bound

Het probleem hiermee is dat het invullen van 0 in de vergelijking alle items met nul stemmen lager zal rangschikken dan die met negatieve stemmen.

Daarom denk ik dat als de betrouwbaarheidsscore wordt gebruikt in een wederkerige vergelijking zoals hierboven (ik maak me natuurlijk zorgen over overflow), dan moet deze opnieuw worden bewerkt om altijd positief te zijn. Een manier om dit te bereiken is:

confidence score = 0.5 + 
    (votetally < 0 ? 
        -(1 - wilson score interval upper bound) :
        wilson score interval lower bound) / 2

Mijn andere zorgen zijn hoe de berekening daadwerkelijk moet worden uitgevoerd, gegeven Lucene.NET en SQL Server. Ik aarzel om de betrouwbaarheidsscore in de Lucene-index te zetten omdat hiervoor de veldcache moet worden gebruikt, wat een enorme impact kan hebben op het geheugenverbruik (zoals eerder vermeld).

Een idee dat ik had was om de relevantiescore van Lucene.NET te krijgen en vervolgens een parameter met tabelwaardeom de score naar SQL Server te streamen (samen met de id’s van de te selecteren items), waarna ik de berekening zou uitvoeren met de betrouwbaarheidsscore en vervolgens de gegevens correct geordend zou retourneren .

Zoals eerder vermeld, zijn er nog een heleboel andere vragen die ik hierover heb, en de antwoorden beginnen dingen in te kaderen en zullen zich blijven uitbreiden naarmate de vraag en de antwoorden zich ontwikkelen.


Antwoord 1, autoriteit 100%

De antwoorden die u zoekt, kunnen echt niet worden gevonden met alleen luceen. U hebt rangschikkings- en groeperingsalgoritmen nodig om de gegevens te filteren en te begrijpen en hoe deze verband houden. Lucene kan u helpen om genormaliseerde gegevens te krijgen, maar daarna heeft u het juiste algoritme nodig.

Ik raad je aan een of alle van de volgende boeken te lezen, ze zullen je helpen met rekenen en je in de goede richting wijzen:

Algoritmen van het intelligente web

Collectieve intelligentie in actie

Collectieve intelligentie programmeren


Antwoord 2, autoriteit 40%

De luceenindex heeft de volgende velden:

  • Titel
  • Vraag
  • Geaccepteerd antwoord (of hoog gestemd antwoord als er geen geaccepteerd antwoord is)
  • Alle antwoorden gecombineerd

Dit zijn allemaal velden die worden geanalyseerd. Normalisatie van lengte is uitgeschakeld om betere controle over de score te krijgen.

De bovengenoemde volgorde van de velden weerspiegelt ook hun belang in aflopende volgorde. Dat wil zeggen, als de vraagovereenkomst in titel belangrijker is dan in het geaccepteerde antwoord, blijft al het andere hetzelfde.

Het aantal upvotes is voor de vraag en het beste antwoord kan worden verkregen door die velden een boost te geven. Maar het onbewerkte aantal stemmen kan niet worden gebruikt als boost-waarden, omdat dit de resultaten dramatisch kan vertekenen. (Een vraag met 4 upvotes krijgt twee keer de score van één met 2 upvotes.) Deze waarden moeten agressief worden gedempt voordat ze als boostfactor kunnen worden gebruikt. Het gebruik van een natuurlijke logaritme (voor upvotes >3) ziet er goed uit.

Titel kan worden verhoogd met een waarde die iets hoger is dan die van de vraag.

Hoewel het onderling koppelen van vragen niet erg gebruikelijk is, kan het hebben van een eenvoudig pagerank-achtig gewicht voor een vraag interessante resultaten opleveren.

Ik beschouw tags van de vraag niet als zeer waardevolle informatie voor zoeken. Tags zijn handig als je gewoon door de vragen wilt bladeren. Meestal maken tags deel uit van de tekst, dus zoeken naar de tags zal overeenkomen met de vraag. Dit staat echter open voor discussie.

Een typische zoekopdracht wordt uitgevoerd op alle vier de velden.

+(title:query question:query accepted_answer:query all_combined:query)

Dit is een globale schets en er zijn aanzienlijke aanpassingen nodig om de juiste boost-waarden en juiste gewichten voor zoekopdrachten te krijgen, indien nodig. Experimenten zullen de juiste gewichten laten zien voor de twee dimensies van kwaliteit – relevantie en belang. Je kunt het ingewikkeld maken door recentheid als een rangordeparameter in te voeren. Het idee hier is dat als een probleem zich voordoet in een bepaalde versie van het product en in latere revisies wordt opgelost, de nieuwe vragen nuttiger kunnen zijn voor de gebruiker.

Er kunnen enkele interessante wendingen aan het zoeken worden toegevoegd. Een vorm van standaard zoeken op synoniemen kan nuttig zijn als er slechts “enkele” overeenkomende resultaten worden gevonden. Bijvoorbeeld, “java heap size verkleinen” is hetzelfde als “java heap size verkleinen”. Maar dan betekent het ook dat ‘kaart verkleinen’ begint met overeenkomen met ‘kaart verkleinen’. (Spellingcontrole ligt voor de hand, maar ik veronderstel dat programmeurs hun zoekopdrachten correct zouden spellen.)


Antwoord 3, autoriteit 20%

Je hebt waarschijnlijk meer nagedacht over dit onderwerp dan de meeste mensen die je zullen proberen te antwoorden (een deel van de reden waarom het een dag is geweest en ik denk dat ik je eerste reactie ben). Ik ga gewoon proberen je laatste drie vragen aan te pakken, omdat er gewoon veel is waar ik geen tijd voor heb, en ik denk dat die drie het meest interessant zijn (de fysieke implementatievragen gaan waarschijnlijk om te eindigen als ‘kies iets en pas het aan naarmate je meer leert’).

stemgegevensIk weet niet zeker of stemmen iets relevanter maken voor een zoekopdracht, eerlijk gezegd, ze worden alleen maar populairder. Als dat logisch is, probeer ik te zeggen dat of een bepaald bericht relevant is voor uw vraag, grotendeels onafhankelijk is van of het relevant was voor andere mensen. dat gezegd hebbende, is er waarschijnlijk op zijn minst een zwakke correlatie tussen interessante vragen en de vragen die mensen zouden willen vinden. Stemgegevens zijn waarschijnlijk het nuttigst bij het uitvoeren van zoekopdrachten die puur op gegevens zijn gebaseerd, b.v. “meest populaire” type zoekopdrachten. Bij generieke, op tekst gebaseerde zoekopdrachten zou ik in eerste instantie waarschijnlijk geen gewicht aan stemmen geven, maar zou ik overwegen te werken aan een algoritme dat misschien een klein gewicht geeft voor het sorteren (dus niet de geretourneerde resultaten, maar een kleine boost voor de volgorde van hen).

antwoordenIk ben het eens met je benadering hier, onder voorbehoud van wat testen; onthoud dat dit een iteratief proces zal moeten zijn op basis van gebruikersfeedback (je moet dus statistieken verzamelen over of zoekopdrachten succesvolle resultaten voor de zoeker hebben opgeleverd)

overigVergeet ook de score van de gebruiker niet. Gebruikers krijgen dus ook punten op SO, en dat heeft invloed op hun standaardrangschikking in de antwoorden van elke vraag die ze beantwoorden (het lijkt erop dat het vooral bedoeld is voor het doorbreken van antwoorden met hetzelfde aantal hobbels)


Antwoord 4, autoriteit 20%

Relevantie bepalen is altijd lastig. Je moet erachter komen wat je probeert te bereiken. Probeert uw zoekopdracht een exacte overeenkomst te geven voor een probleem dat iemand zou kunnen hebben of probeert u een lijst met recente items over een onderwerp te geven?

Als je eenmaal hebt bedacht wat je wilt teruggeven, kun je kijken naar het relatieve effect van elke functie die je indexeert. Dat zal een ruwe zoektocht op gang brengen. Van daaruit pas je aan op basis van gebruikersfeedback (ik raad aan om impliciete feedback te gebruiken in plaats van expliciete, anders irriteer je de gebruiker).

Wat indexering betreft, moet u proberen de gegevens zo in te voeren dat elk item alle informatie heeft die nodig is om het te rangschikken. Dit betekent dat u de gegevens van een aantal locaties moet halen om deze op te bouwen. Sommige indexeringssystemen hebben de mogelijkheid om waarden toe te voegen aan bestaande items, waardoor het gemakkelijk zou zijn om scores aan vragen toe te voegen wanneer de volgende antwoorden binnenkwamen. Eenvoud zou ervoor zorgen dat u de vraag zo nu en dan opnieuw opbouwt.


Antwoord 5, autoriteit 20%

Ik denk dat Lucene niet geschikt is voor deze baan.
Je hebt iets heel snel nodig met een hoge beschikbaarheid… zoals SQL
Maar wil je open source?

Ik raad je aan om Sphinx te gebruiken – http://www.sphinxsearch.com/
Het is veel beter, en ik spreek met ervaring, ik heb ze allebei gebruikt.

Sfinx is geweldig. Echt.

Other episodes