Эффективное соединение/слияние на основе совпадающей части строки

Question

Я пытаюсь объединить две таблицы на основе того, содержится ли строка из первой таблицы в части длинной строки во второй таблице. Я использую PROC SQL в SAS, но также могу использовать шаг данных вместо SQL-запроса.

Этот код отлично работает на небольших наборах данных, но быстро увязывается, так как он должен составлять тонну сравнений. Было бы хорошо, если бы это была простая проверка равенства, но использование функции index() делает ее жесткой.

proc sql noprint; 
    create table matched as 
    select A.*, B.* 
    from search_notes as B, 
     names as A 
    where index(B.notes,A.first) or 
     index(B.notes,A.last) 
    order by names.name, notes.id; 
quit; 
run; 

B.Notes является 2000 символов (иногда полностью заселен) блок текста, и я ищу какого-либо результата, который содержит либо имя или фамилию от А.

Я не думаю, Я получаю любое преимущество в скорости от выполнения этого в два этапа, поскольку он уже должен сравнивать каждую строку A с каждой строкой B (поэтому проверка как для первого, так и для последнего имени не является узким местом).

Когда я запустил его, я получил NOTE: The execution of this query involves performing one or more Cartesian product joins that can not be optimized. в своем журнале. Запуск с наблюдениями A = 4000 и B = 100 000 наблюдений занимает 30 минут, чтобы произвести ~ 1000 матчей.

Есть ли способ это оптимизировать?

Answer 1

Это частичный ответ, что делает его запустить 4-5X быстрее, но это не является идеальным (это помогает в моем случае, но не обязательно будет работать в общем случае оптимизации декартова произведения).

У меня изначально было 4 отдельных индекса(), как в моем примере (у моего упрощенного образца было 2 для A.first и A.last).

Я смог реорганизовать все 4 из этих операторов index() (плюс 5-й я собирался добавить) в регулярное выражение, которое решает ту же проблему. Он не вернет идентичный набор результатов, но я думаю, что он фактически возвращает лучше результатов, чем 5 отдельных индексов, так как вы можете указать ребра слов.

В datastep где я очистить имена для согласования, я создаю следующую закономерность:

pattern = cats('/\b(',substr(upcase(first_name),1,1),'|',upcase(first_name),').?\s?',upcase(last_name),'\b/'); 

Это должно создать регулярное выражение вдоль линий /\b(F|FIRST).?\s?LAST\b/, которые будут соответствовать ничего подобного F. Last, First Last, Flast @ электронная почта.com и т. д. (есть комбинации, которые он не подбирает, но меня интересовали только комбинации, которые я наблюдаю в своих данных). Использование '\ b' также не позволяет вещам, где FLAST оказывается таким же, как начало/конец слова (например, «Эдвард Ло» подходит к «Красноречию»), которого я с трудом избегаю с помощью index()

Тогда я мой SQL присоединиться, как это:

proc sql noprint; 
create table matched as 
    select B.*, 
      prxparse(B.pattern) as prxm, 
      A.* 
    from search_text as A, 
     search_names as B 
    where prxmatch(calculated prxm,A.notes) 
    order by A.id; 
quit; 
run; 

Будучи в состоянии составить регулярное выражение один раз для каждого имени в B, а затем запустить его на каждой части текста в, кажется, значительно быстрее, чем пара индексов (не уверен в случае регулярного выражения по сравнению с одним индексом).

Запуск с A = 250 000 обс и B = 4000 обс, потребовалось примерно 90 минут времени процессора для метода index(), в то же время с prxmatch() потребовалось всего 20 минут времени процессора.

Answer 2

Декартовой продукт может быть лучшим для ваших данных, но вот что попробовать. То, что я делаю, это использовать CALL EXECUTE() на шаге данных для создания шага в шаге данных. Это означает, что вам нужно только перевести каждую таблицу один раз. Тем не менее, на вашем письменном шаге будет установлено 4000 условий IF/THEN. Это приводит к тому, что время выполнения на моих примерах составляет от 55 секунд до 40 секунд. Это будет примерно на 24 минуты ниже ваших 30 минут, если соотношение сохраняется.

Я оставил этот вопрос открытым. Может быть, кто-то может придумать лучший метод.

%let n=50; 
data B; 
format notes $&n..; 
choose = "ABCDEFGHIJLKMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; 
do j=1 to 9000000; 
    notes = ""; 
    do i=1 to floor(5 + ranuni(123)*(&n-5)); 
     r = floor(ranuni(123)*62+1); 
     notes = catt(notes,substr(choose,r,1)); 

    end; 
    output; 
    drop r choose i; 
end; 
run; 

data a; 
choose = "ABCDEFGHIJLKMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; 
format first last $2.; 
do i=1 to 62 by 2; 
    first = strip(substr(choose,i,1)); 
    first = catt(first,first); 
    last = strip(substr(choose,i+1,1)); 
    last = catt(last,last); 
    output; 
end; 
drop choose ; 
run; 

proc sql noprint; 
    create table matched as 
    select A.*, B.* 
    from B as B, 
     A as A 
    where index(B.notes,A.first) or 
     index(B.notes,A.last) 
    order by B.notes, a.i; 
quit; 

options nosource; 
data _null_; 
set a end=l; 
if _n_ = 1 then do; 
    call execute("data matched2; set B;"); 
    call execute("format First Last $2. i best.;"); 
end; 

format outStr $200.; 
outStr = "if index(notes,'" || first || "') or index(notes,'" || last || "') then do;"; 
call execute(outStr); 

outStr = "first = '" || first || "';"; 
call execute(outStr); 
outStr = "last = '" || last || "';"; 
call execute(outStr); 
outStr = "i = " || i || ";"; 
call execute(outStr); 
call execute("output; end;"); 

if l then do; 
    call execute("run;"); 
end; 
run; 

proc sort data=matched2; 
by notes i; 
run; 

Answer 3

Это не похоже на хороший кандидат на PROC SQL. Если я правильно понимаю, вы хотите сравнить каждую строку в search_notes с каждой строкой в ​​names (следовательно, декартово произведение). Более традиционный шаг данных программа может быть легче понять и, возможно, более эффективным:

data matched; 
    set search_notes; 
    do _i_=1 to nobs; 
     set names point=_i_ nobs=nobs; 
     if index(notes,first) 
     or index(notes,last) then output; 
     end; 
    drop _i_; 
run; 
proc sort data=matched; 
    by vendor_name, claimant_id; 
run;