SP to parse string adding synonimes from table

[inspireuk]

The easiest way for me to explain what I'm trying to do is show an example.

I have the following tables:

WORDS
WordID Word
1 1,000,000
2 a million
3 one million

WORDLINKS
WordID WordLinkID
1 2
1 3
2 1
2 3
3 1
3 2

I would then pass the following sentance into the SP
a million times a day

What the SP needs to do is parse the string and find all the phrases within that match the words in the WORDS table. It would then take the WordID and do a lookup in the WORDLINKS table to find all the possible alternatives/synonimes.

The result would be in the following form:
{a million|1,000,000|one million} times a day

the matched phrase has been wrapped in {} with each matched alternatives/synonimes seperated by a pipe |.

there would be multiple phrases in each input string and possibly nested words
eg in the example above the phrase 'one million', 'one' could have an alternative of '1' in which case the output would be:
{a million|1,000,000|{one|1} million} times a day

i hope this makes sense. any help would really be appreciated.

Thanks

Josh

[azimmer]

It's going to be a long one... (But a promise is a promise.) What makes it a bit more difficult is the nested replacements (whose proper handling I'm still not 100% sure of):

• have it greedy or non-greedy (if you have replacements both for 'one million' and 'one' which one has precedence)?
• If any replacement would result in an expanded string that could be further replaced, what to do? (I.e.: replacements: '1'->'one', 'one million'->'a million', what should the output be for '1 million'? And if replacements are '1'->'one', 'one million'->'1,000,000', what should the output be for '1 million'?)

The code below is greedy and processes nested replacements only to the length of the replaced term and not including the term being replaced (see examples at the end). It has two functions because the SQL Server wouldn't take the default value (don't know why) and I've had no more time to play around with it. You only need to use the one without the underscore.

So here goes the code:

create function _syno (@instr as varchar(1000), @term_replace as bit = 0)
returns varchar(1000)
as
begin
declare @pos as int
declare @current_str as varchar(1000)
declare @syno_term as varchar(1000)
declare @replaced_length as int
declare @outstr as varchar(1000)
set @outstr=''
 
set @pos=1
while @pos<=len(@instr)
begin
    -- try from current position on
    set @current_str=right(@instr,len(@instr)-@pos+1)
    declare current_replacements cursor local for
        -- this is tricky
        select distinct top 1 with ties w.word [syno_term], len(w2.word) [replaced_length]
        from words w, wordlinks l, words w2
        where w.wordid=l.wordlinkid
        and (l.wordid=w2.wordid)
        and charindex(w2.word,@current_str)=1
        and (@term_replace=0 or (w2.word<>@current_str))
        order by len(w2.word) desc
    open current_replacements
    fetch next from current_replacements into @syno_term, @replaced_length
    if @@fetch_status = 0    -- there are replacements
    begin
        set @outstr=@outstr+'{'+left(@current_str,@replaced_length)
        -- iterate on current set of replacements (recursivity)
        while @@fetch_status = 0
        begin
            set @syno_term=dbo._syno(@syno_term, 1)
            set @outstr=@outstr+'|'+@syno_term
            fetch next from current_replacements into @syno_term, @replaced_length
        end
        set @outstr=@outstr+'}'
        set @pos=@pos+@replaced_length
    end
    else
    begin
        set @outstr=@outstr+left(@current_str,1)
        set @pos=@pos+1
    end
    deallocate current_replacements
end
return @outstr 
end
GO
 
create function syno (@instr as varchar(1000))
returns varchar(1000)
as
begin
return dbo._syno(@instr,0)
end
GO
 

Note: I found the easiest way to get the code itself (without line numbers) is to "Reply" to the message and copy-paste whatever is between '[ CODE]' and '[ /CODE]'.

My WORDS and WORDLINKS tables are as follows:

WordID      Word                                               
----------- -------------------
1           1,000,000
2           a million
3           one million
4           one
5           1
 
WordID      WordLinkID  
----------- ----------- 
1           2
1           3
2           1
2           3
3           1
3           2
4           5
 

Examples and usage:

print dbo.syno('I hope you run it a million times')
 

results: I hope you run it {a million|1,000,000|{one|1} million} times

print dbo.syno('I hope you run it one million times')
 

results: I hope you run it {one million|1,000,000|a million} times
(note how it will replace 'one million', and will process the 'one' in the 'one million' because that's the whole term to be replaced in the first place)

print dbo.syno('I hope someone runs it one million times')
 

results: I hope some{one|1} runs it {one million|1,000,000|a million} times

Hope it helps. I don't say it's impossible to refine it (especially in the handling of nested replacements) but I believe it's a good start.

P.S.: It, indeed, would have been a rather steep learning curve from a very basic level...

[inspireuk]

This is ammmaazzing! I can't thank you enough :)

However :) just a couple more things if you have the time. Would it be possible only to match full words and with regards to the nested replacements i think i may just programmically recall the sp for small parts if needed so no recursion needed (sorry).

the precedence i think should be for the longer phrase.

let me know if there is anything else.

Josh

[inspireuk]

so i've been playing with what you gave me. i've changed it to a stored procedure as i'm no longer doing recursion. if you get a chance can you look at the code below - it does seem to be working but i'm not sure whether it is written the best way. Thanks again for all your time.

ALTER PROCEDURE ParseString
    @instr as varchar(max)
AS
 
    declare @pos as int
    declare @current_str as varchar(max)
    declare @syno_term as varchar(max)
    declare @replaced_length as int
    declare @outstr as varchar(max)
 
    set @outstr = ''
    set @pos=1
    while @pos<=len(@instr)
    begin
        -- try from current position on
        set @current_str=right(@instr,len(@instr)-@pos+1)
        declare current_replacements cursor local for
            -- this is tricky
            select distinct top 1 with ties w.word [syno_term], len(w2.word) [replaced_length]
            from words w, LinkedWords l, words w2
            where w.wordid=l.LinkedWordID
            and (l.wordid=w2.wordid)
            and charindex(w2.word,@current_str)=1
            and right(left(@current_str, len(w2.word)+1),1) = ' '
            order by len(w2.word) desc
        open current_replacements
        fetch next from current_replacements into @syno_term, @replaced_length
        if @@fetch_status = 0    -- there are replacements
        begin
            set @outstr=@outstr+'{'+left(@current_str,@replaced_length)
            -- iterate on current set of replacements (recursivity)
            while @@fetch_status = 0
            begin
                --set @syno_term=ammuser._syno(@syno_term, 1)
                set @outstr=@outstr+'|'+@syno_term
                fetch next from current_replacements into @syno_term, @replaced_length
            end
            set @outstr=@outstr+'} '
            set @pos=@pos+@replaced_length+1
        end
        else
        begin
            if charindex(' ',@current_str) = 0
                begin
                    set @outstr=@outstr+@current_str
                    set @pos=@pos+len(@current_str)                
                end
            else
                begin
                    set @outstr=@outstr+left(@current_str,charindex(' ',@current_str))
                    set @pos=@pos+charindex(' ',@current_str)
                end
        end
        deallocate current_replacements
    end
    SELECT @outstr
 

[azimmer]

so i've been playing with what you gave me. i've changed it to a stored procedure as i'm no longer doing recursion. if you get a chance can you look at the code below - it does seem to be working but i'm not sure whether it is written the best way. Thanks again for all your time.

ALTER PROCEDURE ParseString
    @instr as varchar(max)
AS
 
    declare @pos as int
    declare @current_str as varchar(max)
    declare @syno_term as varchar(max)
    declare @replaced_length as int
    declare @outstr as varchar(max)
 
    set @outstr = ''
    set @pos=1
    while @pos<=len(@instr)
    begin
        -- try from current position on
        set @current_str=right(@instr,len(@instr)-@pos+1)
        declare current_replacements cursor local for
            -- this is tricky
            select distinct top 1 with ties w.word [syno_term], len(w2.word) [replaced_length]
            from words w, LinkedWords l, words w2
            where w.wordid=l.LinkedWordID
            and (l.wordid=w2.wordid)
            and charindex(w2.word,@current_str)=1
            and right(left(@current_str, len(w2.word)+1),1) = ' '
            order by len(w2.word) desc
        open current_replacements
        fetch next from current_replacements into @syno_term, @replaced_length
        if @@fetch_status = 0    -- there are replacements
        begin
            set @outstr=@outstr+'{'+left(@current_str,@replaced_length)
            -- iterate on current set of replacements (recursivity)
            while @@fetch_status = 0
            begin
                --set @syno_term=ammuser._syno(@syno_term, 1)
                set @outstr=@outstr+'|'+@syno_term
                fetch next from current_replacements into @syno_term, @replaced_length
            end
            set @outstr=@outstr+'} '
            set @pos=@pos+@replaced_length+1
        end
        else
        begin
            if charindex(' ',@current_str) = 0
                begin
                    set @outstr=@outstr+@current_str
                    set @pos=@pos+len(@current_str)                
                end
            else
                begin
                    set @outstr=@outstr+left(@current_str,charindex(' ',@current_str))
                    set @pos=@pos+charindex(' ',@current_str)
                end
        end
        deallocate current_replacements
    end
    SELECT @outstr
 

Is good that you have the ambition and time to play around with it as I have very little time at the moment. Still I've been thinking about whole word replacements. One of the tough issues is that you need to have a word terminator at both ends of the term to be replaced - and word terminators come in many forms (not only space, but period, comma, semicolon, dash, new line, tab, etc as well - perhaps whatever is not a letter (but then what about '@' and digits?).) It should somehow be taken care of in the cursor select to make sure no false replacements are signaled (an that's not easy). Alternatively it may be possible to modify the select so that it sometimes gives false possibilities and then check and disregard them (but that's ain't easy either).

Slowly we're venturing into the realms of grep and awk - implemented in a SQL Server SP :-) (Just kidding; we're miles away.)