5 Replies Latest reply: Jan 15, 2013 4:09 AM by Geert Joosten RSS

    Find first record starting with most extensive ability

    Geert Joosten
      Hi,

      This question might have been asked before but I don't know how to describe it in the search field.

      There are 3 records with 2 fields (id, name). These records are:
      1,Amsterdam
      2,Amster
      3,Am

      I want to find the record that holds the most possible information:
      searching Amsterdam must return 1; searching Amsterdamned must return 1; searching America must return 3; searching United must return 0 (or null).

      So the logic is to search for the whole string and return the id when found. If not found remove the most right character and search until found or a empty string.

      Since this logic has to be a part of SQL I wonder if there is a smart way (without writing a PL/SQL function) to solve this?

      I'm curious.

      Geert.
        • 1. Re: Find first record starting with most extensive ability
          Keith Jamieson
          In orde rto check the similarity of two words , you can use the utl_match package.

          eg
            SELECT UTL_MATCH.EDIT_DISTANCE_SIMILARITY('Amsterdam','Amsterdamed') FROM DUAL;
            SELECT UTL_MATCH.EDIT_DISTANCE_SIMILARITY('Amster','Amsterdamed') FROM DUAL;
            SELECT UTL_MATCH.EDIT_DISTANCE_SIMILARITY('dublin','Amsterdam') FROM DUAL;
          There are other comparison procedures and functions as well.
          • 2. Re: Find first record starting with most extensive ability
            BluShadow
            Also sounds a bit like the longest common substring problem...

            http://en.wikipedia.org/wiki/Longest_common_substring_problem
            SQL> ed
            Wrote file afiedt.buf
            
              1  with t as (select 'Antidisestablishmentarianism' as str1, 'Theestablishmentist' as str2 from dual)
              2  --
              3  select str, length(str) as len
              4  from (
              5        select distinct
              6               substr(str2,rn1,rn2-rn1) as str
              7              ,dense_rank() over (order by length(substr(str2,rn1,rn2-rn1)) desc) as rnk
              8        from t, (select rownum rn1 from t connect by rownum <= length(str2)+1)
              9              , (select rownum rn2 from t connect by rownum <= length(str2)+1)
             10        where rn2 > rn1
             11        and instr(str1, substr(str2,rn1,rn2-rn1)) > 0
             12       )
             13* where rnk = 1
            SQL> /
            
            STR                        LEN
            ------------------- ----------
            establishment               13
            obviously it would need some tweaking to get it working against multiple words
            • 3. Re: Find first record starting with most extensive ability
              Frank Kulash
              Hi, Geert,

              So you're only interested in strings that start the same way? That is, the fact that 'Amsterdam' and 'United' have the substring 'te' in common doesn't matter, because 'te' comes in the middle of those strings.

              If that's so, you can use LIKE to compare the strings.
              WITH   got_r_num    AS
              (
                   SELECT     p.place_name
                   ,     a.place_id
                   ,     a.place_name     AS a_place_name          -- Not needed, nut may be nice
                   ,     RANK () OVER ( PARTITION BY  p.place_name
                                         ORDER BY          LENGTH (a.place_name)  DESC
                                  )  AS r_num
                   FROM          possible_places  p
                   LEFT OUTER JOIN      actual_places       a  ON  p.place_name LIKE a.place_name || '%'
              )
              SELECT       place_name
              ,       NVL (place_id, 0)     AS place_id     -- or, if you want NULL, just place_id
              ,       a_place_name                       -- if wanted
              FROM       got_r_num
              WHERE       r_num     = 1
              ORDER BY  place_name
              ;
              Whenever you have a problem, please post CREATE TABLE and INSERT statments for some sample data, like this:
              CREATE TABLE     actual_places
              (   place_id     NUMBER (6)     PRIMARY KEY
              ,   place_name     VARCHAR2 (20)     
              );
              
              INSERT INTO actual_places (place_id, place_name) VALUES (1,  'Amsterdam');
              INSERT INTO actual_places (place_id, place_name) VALUES (2,  'Amster');
              INSERT INTO actual_places (place_id, place_name) VALUES (3,  'Am');
              
              
              
              CREATE TABLE     possible_places
              (   place_name     VARCHAR2 (20)     PRIMARY KEY
              );
              
              INSERT INTO possible_places (place_name) VALUES ('Amsterdam');
              INSERT INTO possible_places (place_name) VALUES ('Amsterdamned');
              INSERT INTO possible_places (place_name) VALUES ('America');
              INSERT INTO possible_places (place_name) VALUES ('United');
              Also, post the results you want from that data, exactly as you want to see them. The query above produces this output:
              PLACE_NAME             PLACE_ID A_PLACE_NAME
              -------------------- ---------- --------------------
              America                       3 Am
              Amsterdam                     1 Amsterdam
              Amsterdamned                  1 Amsterdam
              United                        0
              See the forum FAQ {message:id=9360002}
              • 4. Re: Find first record starting with most extensive ability
                stefan nebesnak
                See statement below..
                SELECT t2.place_id 
                FROM   (SELECT t.*, 
                               Decode(( Instr(Lower('&value'), Lower(t.place_name), 1, 
                               1) ), 1, Length(t.place_name), 
                                     0) AS len 
                        FROM   actual_places t 
                        ORDER  BY len DESC) t2 
                WHERE  t2.len != 0 
                       AND rownum = 1; 
                AmsteRdamX --1
                Amsterdam --1
                AmsterX --2
                Amster --2
                aMs --3
                am --3
                Am --3
                test --NULL                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               
                • 5. Re: Find first record starting with most extensive ability
                  Geert Joosten
                  Hi Stefan,

                  Thank you for this solution. Works just like I wanted.

                  Regards,
                  Geert.