WN - Matchning av texter, STORT antal

WN (https://www.wn.se/forum/index.php)

- Serversidans teknologier (https://www.wn.se/forum/forumdisplay.php?f=4)

- - Matchning av texter, STORT antal (https://www.wn.se/forum/showthread.php?t=1057881)

secag

2013-05-10 16:56

Matchning av texter, STORT antal

Hej,

Jag har cirka 80 000 texter där det KAN finnas dubletter, inte precis exakt men det skiljer väl sig på något ord/punkt/tecken.

Då jag inte har ork eller tid för att gå igenom 1 och 1 så kanske det finns någon smart teknik som kan leta fram ganska stora likheter i texter? Jag har allting sparat i en databas och i textfiler. Någon som vet vilken teknik jag ska använda?

CotopaXi

2013-05-10 18:15

Om du förutsätter att t.ex det första och det sista ordet är samma för dubbletterna borde du kunna få ner 80 000 olika texter till ett betydligt minde antal där det kan finnas dubbletter.

Om det bara skiljer något tecken bör ju dubbletterna också ha ungefär samma längd, du skulle ju kunna kolla hur många som diffar på mindre än 10-tecken i längd. Du skulle också kunna jämföra filstorlek på textfilerna och kolla vilka som diffar mindre än x-bytes i storlek.

Att implementera dessa två borde inte ta lång tid om du behärskar programmering.

Conny Westh

2013-05-10 18:32

Jag tycker man kan ta texterna och tokenisera de enskilda orden. sen räknar man hur många ord som är lika och hur många ord det finns totalt.

Sen delar man antalet lika ord med totala antalet ord och får då en procentsiffra som kan ge en hyfsad uppfattning hur lika texterna är.

Sen är det bara att sortera på de med störst likhet och gå in och kika manuellt hur väl det stämmer.

Man kan även göra en ordanalys så man räknar antalet lika tecken i ett enskilt ord för att se om det finns många ord som är snarlika (skiljer 1-2 tecken så kan det vara en felstavning).

yakuzaemme

2013-05-10 18:59

Har du hittat något eller ska jag slänga ihop ett program?

secag

2013-05-10 20:10

om du vill slänga ihop vore det schysst.

försöker göra ngn sak på det formulär som jag sparar data i som kollar om det redan finns men failar. xD

yakuzaemme

2013-05-10 20:39

http://www.speedyshare.com/jReHE/DublettFinder.rar

Går efter första/sista ord samt storlek. Inte den mest pålitliga men ska nog ge en bra fingervisning.

Skulle kunna använda LINQ's Except men för mycket data skulle laddas in i minnet, detta verkar fungera hyffsat. Säg gärna till hur det fungerade mot större textfiler.

secag

2013-05-10 21:31

Det funkade bra tyckte jag men nu när jag tänkte efter vill jag ha det som serverkod. jag har gjort ett litet exempel här.

Men problemet är att jag tar hela texter och kopierar in det och då kollar den ju denna kod om hela texten är lika med någon annan. Men jag vill ha detta som Conny beskrev: kolla alla ord som stämmer genom alla ord som finns i strängen man söker med. Hur kan jag trimma denna så det passar?

PHP-kod:


		
			
$parts = explode(" ", trim($_POST["text"]));

        $likes = "";

        $i = 1;

        foreach($parts as $part) {

            $likes .= "`fact` LIKE '%".$database->real_escape_string($part)."%'";

            if($i < count($parts)) {

                $likes .= " AND ";

            }

            $i++;

        }

        if(strlen($likes) > 0) {

            $query = $database->query("SELECT * FROM facts WHERE ".$likes);

            if($query->num_rows > 0) {

                echo '<table class="table table-striped table-bordered table-condensed">';

                $arr = result_to_array($query);

                foreach($arr as $ar) {

                    echo '<tr><td>'.$ar["id"].'</td><td>'.$ar["fact"].'</td></tr>';

                }

                echo '</table>';

            }

        }

tartareandesire

2013-05-10 23:32

Det finns ett flertal olika färdiga funktioner i PHP för att jämföra strängar. Hur bra de fungerar beror helt på vilka behov man har men de kan ju enkelt kombineras med diverse egna kontroller.

Conny Westh

2013-05-11 01:12

Här hittade jag en funktion som splittar upp en textsträng i sql så man får varje ord som en egen rad (MS SQL-Server):

Kod:

Create function dbo.SplitString 

    (

        @str nvarchar(4000), 

        @separator char(1)

    )

    returns table

    AS

    return (

        with tokens(p, a, b) AS (

            select 

                1, 

                1, 

                charindex(@separator, @str)

            union all

            select

                p + 1, 

                b + 1, 

                charindex(@separator, @str, b + 1)

            from tokens

            where b > 0

        )

        select

            p-1 zeroBasedOccurance,

            substring(

                @str, 

                a, 

                case when b > 0 then b-a ELSE 4000 end) 

            AS token

        from tokens

      )

    GO

Så här använder man funktionen för att få fram alla orden:

Kod:

select * 

    from dbo.SplitString('Hello John Smith', ' ')

Så här använder man funktionen för att få fram ett specifikt ord:

Kod:

select * 

    from dbo.SplitString('Hello John Smith', ' ')

    where zeroBasedOccurance=1

Conny Westh

2013-05-11 01:36

Här hittade jag en ännu elegantare lösning:

Kod:

CREATE FUNCTION [dbo].[split](

          @delimited NVARCHAR(MAX),

          @delimiter NVARCHAR(100)

        ) RETURNS @t TABLE (id INT IDENTITY(1,1), val NVARCHAR(MAX))

        AS

        BEGIN

          DECLARE @xml XML

          SET @xml = N'<t>' + REPLACE(@delimited,@delimiter,'</t><t>') + '</t>'



          INSERT INTO @t(val)

          SELECT  r.value('.','varchar(MAX)') as item

          FROM  @xml.nodes('/t') as records(r)

          RETURN

        END

För att testa:

Kod:

select * From split('Hello**John**Smith','**')

select * From split('Hello*-*John*-*Smith','*-*')

select * from split('Hello John Smith',' ')

Conny Westh

2013-05-11 03:37

Efter lite testande så kom jag fram till två lämpliga funtioner och lite testdata:

Kod:

CREATE FUNCTION [dbo].[split](

          @delimited NVARCHAR(MAX),

          @delimiter NVARCHAR(100)

        ) RETURNS @t TABLE (id INT IDENTITY(1,1), val NVARCHAR(MAX))

        AS

        BEGIN

          DECLARE @xml XML

          SET @xml = N'<t>' + REPLACE(@delimited,@delimiter,'</t><t>') + '</t>'



          INSERT INTO @t(val)

          SELECT  r.value('.','varchar(MAX)') as item

          FROM  @xml.nodes('/t') as records(r)

          RETURN

        END

Kod:

CREATE FUNCTION [dbo].[similarity]

(

  @text1 NVARCHAR(MAX),

  @text2  NVARCHAR(MAX)

) RETURNS real

AS

BEGIN

  DECLARE @similarity real

  DECLARE @similar real

  DECLARE @total real



  select @total=COUNT(*) from Split(@text2,' ')

  

  select @similar=COUNT(*) from Split(@text1,' ')

  WHERE val In (select val from Split(@text2,' '))

  

  set @similarity = @similar / @total

  RETURN @similarity

END

Lite testkörning:

Kod:

Declare @text1 nVarchar(Max) = 'Hello John Smith the first'

Declare @text2  nVarchar(Max) = 'Hello John Smith the second';

Declare @text3  nVarchar(Max) = 'Hello John Smith the second kalle olle ';



select dbo.similarity(@text1,@text2) -- 0,8 -> 80%

select dbo.similarity(@text1,@text3) -- 0,5 -> 50%

leonard

2013-05-11 15:58

Helt OT; men satan vad sjuk SQL-kod du skriver Conny. Är du en artificiell intelligens från framtiden? :D

Conny Westh

2013-05-11 16:24

SplitString() och Split()-funktionerna hittade jag på någon internetsida men funktionen similarity() har jag knackat ihop, jag har bara testat med några få exempel men den ser ut att funka.

"Articifiell intelligens från framtiden" var ett nytt epitet, He, he :-)

linusoleander

2013-05-11 16:26

Det va väldigt va svårt ni gör de för er själva.
Använd levenshtein-algoritmen för att räkna ut ett normaliserad avstånd mellan två texter. Är värdet mindre än te.x 0.1: lika, annars olika.

7 rader kod i te.x Python eller Ruby.

tartareandesire

2013-05-11 19:32

Citat:

Ursprungligen postat av linusoleander (Inlägg 20469619)

Finns i PHP också, liksom flera andra metoder.

linusoleander

2013-05-11 19:48

Citat:

Ursprungligen postat av tartareandesire (Inlägg 20469627)

Finns i PHP också, liksom flera andra metoder.

Jaha, vad vill du ha sagt med de? :p

tartareandesire

2013-05-11 23:35

Citat:

Ursprungligen postat av linusoleander (Inlägg 20469628)

Jaha, vad vill du ha sagt med de? :p

Ingenting annat än just det :) Eftersom han hade exempelkod i php ovan så tyckte jag det var värt att nämna :)

mephisto73

2013-05-13 13:06

similar_text (php)?

Alex	2013-05-14 12:01

Hur många ord är varje text på? Levenshtein och smiliar_text drar ruskigt mycket resurser och det kommer ta otroligt lång tid om det är mer än 20 ord per text. Däremot borde MySQL klara av det med fulltext-index.

Utan att ha testat och bara genom att spekulera tror jag att du hade kunnat få det gjort rätt snabbt genom att loopa igenom dina texter, fråga databasen efter texten, och där id != iterationsID. Får du ett svar som har någon relevans över säg, 50% (justera efter behov), så kan du vara ganska säker på att den är snarlik eller en dublett. Markera upp den tillsammans med iterationsID och kör en manuell koll efteråt.

Detta är nog den mest eleganta och snabbaste lösningen. Funkar inte den så finns det en del vettiga implementationer av Levenshtein för MySQL ute på nätet som är snabbare än PHP's implementation tillsammans med fulltext-index.

http://dev.mysql.com/doc/refman/5.1/...-language.html

Alla tider är GMT +2. Klockan är nu 14:36.