2

I'm trying to create a search which searches a field for a longest matches possible and then stop.

Here's the basic idea in Python for single match:

import re


def generate(txt: str) -> list:
    s = re.split(r'\s+', txt)
    chunksize = len(s)
    for curr_chunksize in reversed(range(1, chunksize + 1)):
        for pos in range(chunksize - curr_chunksize + 1):
            yield " ".join(s[pos:pos + curr_chunksize])


if __name__ == '__main__':
    txt = 'I think The Thing was great'
    for i in generate(txt):
        print(i)

This generates a moving window which gets smaller and smaller:

I think The Thing was great
I think The Thing was
think The Thing was great
I think The Thing
think The Thing was
The Thing was great
I think The
think The Thing
The Thing was
Thing was great
I think
think The
The Thing
Thing was
was great
I
think
The
Thing
was
great

The search will be:

if __name__ == '__main__':
    txt = 'I think The Thing was great and Back to the Future too'

    search = ['The Thing', 'The', 'Thing', 'Back to the Future', 'Back to the Future 2']
    # Sort by length, reversed (longest first)
    search = sorted(search, reverse=True, key=lambda x: len(x))

    # longest matches (start pos index, end pos index)
    reserved_substring_range: List[Tuple[int, int]] = []

    for i in generate(txt):
        for s in search:
            if s == i:
                pos = txt.find(s)
                can_add = True
                for r in reserved_substring_range:
                    start, end = r
                    if start <= pos <= end and start <= pos + len(i) <= end:
                        can_add = False
                if can_add:
                    reserved_substring_range.append((pos, pos + len(i)))
                break

    for r in reserved_substring_range:
        start, end = r
        print(txt[start:end])

Which outputs:

Back to the Future
The Thing

Now to PostgreSQL (v15.3) side:

CREATE TABLE movies (
  id    INT PRIMARY KEY GENERATED ALWAYS AS IDENTITY,
  title TEXT NOT NULL DEFAULT '' CHECK ( title != '' ),
  year  SMALLINT NOT NULL CHECK ( year > 0 )
);

INSERT INTO movies (title, year) VALUES 
('The Thing', 1982), ('The Thing', 2011),
('The', 9999), ('Thing', 9999),
('Back to the Future', 9999), ('Back to the Future 2', 9999);

Search function which searches from movies table and field title:

SELECT * FROM search('I think The Thing was great and Back to the Future too', NULL::movies, 'title');

And it should return:

id title              year
5  Back to the Future 9999
1  The Thing          1982
2  The Thing          2011

Current attempt which also returns 'The' and 'Thing' incorrectly:

CREATE OR REPLACE FUNCTION search(
    query TEXT, -- search query
    _table ANYELEMENT,  -- source table NULL::<tablename>
    _field TEXT -- source field 'title'
)
    RETURNS SETOF ANYELEMENT
AS $$
DECLARE
    a TEXT[] := regexp_split_to_array(query, '\s+'); -- array of words
    l INT := cardinality(a); -- length of a
    _q TEXT; -- query
    _from INT; -- array start
    _to INT; -- array end
BEGIN
    IF l = 0 THEN
        -- empty query
        RETURN;
    END IF;

    FOR curr_chunk_size IN REVERSE l .. 1 LOOP
        FOR pos IN 0 .. (l - curr_chunk_size) LOOP
            _from := 1 + pos;
            _to := _from + (curr_chunk_size - 1);
            --RAISE LOG 'ccs: %s pos: %', curr_chunk_size, pos;
            _q := array_to_string(a[_from::int : _to], ' ');
            RAISE LOG 'str: "%"', _q;

            RETURN QUERY EXECUTE format('
                SELECT *
                FROM %s 
                WHERE %I = $1', 
                pg_typeof(_table), _field) 
             USING _q;
  
        END LOOP;
    END LOOP;

    RETURN;
END $$ language plpgsql;

Or is this search possible to create without plpgsql?

DB Fiddle

Edit: I realized there might be more than one matches.

1 Answer 1

0

Perhaps this will satisfy:

SELECT id, title, year
FROM (SELECT DISTINCT
             movies.id, movies.title, movies.year,
             rank() OVER (ORDER BY length(movies.title) DESC)
      FROM regexp_split_to_array('I think The Thing was great', '\s+') AS ss(a)
         CROSS JOIN LATERAL generate_series(1, cardinality(ss.a)) AS u(i)
         CROSS JOIN LATERAL generate_series(1, u.i) AS l(i)
         JOIN movies ON title ~ ('\m' || array_to_string(ss[l.i:u.i], '\s+') || '\M')
     ) AS sub
WHERE rank = 1;

 id │   title   │ year 
════╪═══════════╪══════
  2 │ The Thing │ 2011
  1 │ The Thing │ 1982
(2 rows)
2
  • I realized there might be more than one match. Question edited and new Fiddle with more movies.
    – raspi
    Jul 4, 2023 at 18:31
  • The suggested correct response in your modified question makes no sense: "The Thing" is not the longest match. You have to come up with clear requirements before you can find a solution. Jul 4, 2023 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.