String Comparison - Damerau-Levenshtein Algorithm

When creating a set of test records for a new Identity Insight installation, one of the things you will want to identify are pairs of string values that are similar, but not exact.  This applies to names, attributes, and numbers.

One way to evaluate the difference between two strings is to identify the changes needed to change one string to the other; the fewer the changes, the more similar the strings.  The Damerau-Levenshtein Distance algorithm counts the minimum number of insertions, deletions, substitutions, and transpositions needed to change one string to another.

Here is a Javascript function that implements the Damerau-Levenshtein algorithm.  This was written to run with cscript in a Windows environment.

function fnDamerauLevenshtein(a, b ) {
   
   //Initialize distance matrix
   var d = [];
   for (i = 0; i <= a.length; i++) {
      d[i] = [];
   }
   
   //If either string is zero length, then return the length of the other string (all insertions)
   if (a.length == 0)
      return b.length;
   if (b.length == 0)
      return a.length;
   
   //Populate initial values in matrix
   for(i = 0; i <= a.length; i++)
      d[i][0] = i;
   for(j = 0; j <= b.length; j++)
      d[0][j] = j;
   
   //Populate distance matrix
   for(i = 1; i<= a.length; i++) {
      for(j = 1; j <= b.length; j++) {
         if (a.substring(i-1, i) == b.substring(j-1, j))
            cost = 0;
         else
            cost = 1;
         
         //Levenshtein portion of algorithm, determines insertions, deletions, substitutions
         min1 = d[i - 1][j] + 1;
         min2 = d[i][j - 1] + 1;
         min3 = d[i - 1][j - 1] + cost;
         d[i][j] = Math.min(min1, min2, min3);
         
         //Damerau portion of algorithm, determines transpositions
         if(i > 1 && j > 1)
            if (a.substring(i-1, i) == b.substring(j - 2, j-1) && a.substring(i - 2, i-1) == b.substring(j-1, j))
               d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost);
      }
   }
   
   //The final distance value is stored in the last corner of the matrix
   return d[a.length][b.length];
}

WScript.Echo('Distance between ' + WScript.Arguments.Item(0) + ' and ' + WScript.Arguments.Item(1));
WScript.Echo(fnDamerauLevenshtein(WScript.Arguments.Item(0),WScript.Arguments.Item(1)));

Save the code as DamerauLevenshtein.js.  To test the code, open a command prompt and type:

>cscript DamerauLevenshtein.js accept except

Distance between accept and except
2

>

Display Entity History

This rather ugly Oracle query will display the history of an entity.  This includes each identity's creation, updates, and deletions, plus any merges that occurred.

set pagesize 0
set linesize 1000
define ent = &entity_id

column create_dt format a20
column typ format a20
column subtyp format a20
column result format a200

break on create_dt skip 1 on entity_id on dsrc_acct_id;

select to_char(d.sys_create_dt, 'YYYY-MM-DD HH24:MI:SS') create_dt, 
    coalesce(( select distinct org_entity_id    
               from er_relocation e 
               where e.dsrc_acct_id = d.dsrc_acct_id 
               and action_date = (select min(action_date) 
                                  from er_relocation 
                                  where dsrc_acct_id = e.dsrc_acct_id 
                                  and action_date > d.sys_create_dt)
              )
              ,entity_id) entity_id, 
    dsrc_acct_id, 
    'Account Created' typ, 
    '' subtyp, 
    dsrc_code || ' ' || dsrc_acct result 
from dsrc_acct d 
join dsrc_code c on d.dsrc_id = c.dsrc_id 
where d.entity_id = &ent
    union
select to_char(d.sys_delete_dt, 'YYYY-MM-DD HH24:MI:SS') create_dt, 
    coalesce(( select distinct org_entity_id 
               from er_relocation e 
               where e.dsrc_acct_id = d.dsrc_acct_id 
               and action_date = (select min(action_date)                                              from er_relocation 
                                  where dsrc_acct_id = e.dsrc_acct_id 
                                  and action_date > d.sys_delete_dt)
                )
                ,entity_id) entity_id, 
    dsrc_acct_id, 
    'Account Deleted' typ, 
    '' subtyp, 
    dsrc_code || ' ' || dsrc_acct result 
from dsrc_acct d 
join dsrc_code c on d.dsrc_id = c.dsrc_id 
where d.entity_id = &ent 
and d.sys_delete_dt is not null
    union
select to_char(sys_create_dt, 'YYYY-MM-DD HH24:MI:SS') create_dt, 
    coalesce(( select distinct org_entity_id 
               from er_relocation e 
               where e.dsrc_acct_id = n.dsrc_acct_id 
               and action_date = (select min(action_date) 
                                  from er_relocation 
                                  where dsrc_acct_id = e.dsrc_acct_id 
                                  and action_date > n.sys_create_dt)
               )
               ,entity_id) entity_id, 
    dsrc_acct_id, 
    'Name' typ, 
    '' subtyp, 
    rtrim(coalesce(name_pfx||' ','') || coalesce(first_name||' ','') || coalesce(mid_name||' ','') || coalesce(last_name||' ','') || coalesce(name_gen||' ','') || coalesce(name_sfx,'')) result 
from name n 
where entity_id = &ent
    union
select to_char(sys_create_dt, 'YYYY-MM-DD HH24:MI:SS') create_dt, 
    coalesce(( select distinct org_entity_id 
               from er_relocation e    
               where e.dsrc_acct_id = a.dsrc_acct_id 
               and action_date = (select min(action_date)                                           from er_relocation 
                                  where dsrc_acct_id = e.dsrc_acct_id 
                                  and action_date > a.sys_create_dt)
               )
               ,entity_id) entity_id, 
    dsrc_acct_id, 
    'Address' typ, 
    '' subtyp, 
    rtrim(coalesce(addr1||' ','') || coalesce(addr2||' ','') || coalesce(addr3||' ','') || coalesce(city||' ','') || coalesce(state||',','') || coalesce(postal_code||' ','') || coalesce(country||' ','') || coalesce(country_code,'')) result 
from address a 
where entity_id = &ent
    union
select to_char(sys_create_dt, 'YYYY-MM-DD HH24:MI:SS') create_dt, 
    coalesce(( select distinct org_entity_id 
               from er_relocation e 
               where e.dsrc_acct_id = a.dsrc_acct_id 
               and action_date = (select min(action_date) 
                                  from er_relocation 
                                  where dsrc_acct_id = e.dsrc_acct_id 
                                  and action_date > a.sys_create_dt)
               )
               ,entity_id) entity_id, 
    dsrc_acct_id, 
    'Email' typ, 
    '' subtyp, 
    rtrim(email_addr) result 
from email_addr a 
where entity_id = &ent
    union
select to_char(a.sys_create_dt, 'YYYY-MM-DD HH24:MI:SS') create_dt, 
    coalesce(( select distinct org_entity_id 
               from er_relocation e 
               where e.dsrc_acct_id = a.dsrc_acct_id 
               and action_date = (select min(action_date) 
                                  from er_relocation 
                                  where dsrc_acct_id = e.dsrc_acct_id 
                                  and action_date > a.sys_create_dt)
               )
               ,entity_id) entity_id, 
    dsrc_acct_id, 
    'Attribute' typ, 
    t.attr_type subtyp, 
    t.attr_type || ': ' || a.attr_value result 
from attribute a 
join attr_type t on a.attr_type_id = t.attr_type_id --and a.attr_type_id not in (16,102) 
where entity_id = &ent
    union
select to_char(n.sys_create_dt, 'YYYY-MM-DD HH24:MI:SS') create_dt, 
    coalesce(( select distinct org_entity_id 
               from er_relocation e 
               where e.dsrc_acct_id = n.dsrc_acct_id 
               and action_date = (select min(action_date) 
                                  from er_relocation 
                                  where dsrc_acct_id = e.dsrc_acct_id 
                                  and action_date > n.sys_create_dt)
               )
               ,entity_id) entity_id, 
    dsrc_acct_id, 
    'Number' typ, 
    t.num_type subtyp, 
    t.num_type || ': ' || n.num_value || ' ' || n.num_location result 
from nums n 
join num_type t on n.num_type_id = t.num_type_id 
where entity_id = &ent
    union
select to_char(action_date, 'YYYY-MM-DD HH24:MI:SS') create_dt, 
    dest_entity_id entity_id, 
    dsrc_acct_id, 
    'Entity Merge' typ, 
    '' subtyp, 
    org_entity_id || ' merged into ' || dest_entity_id result 
from er_relocation 
where er_id in (select er_id 
                from er_relocation 
                where (org_entity_id = &ent or dest_entity_id = &ent)
                ) 
order by create_dt, dsrc_acct_id, typ, subtyp, result;