Как фильтровать перекрывающиеся строки в большом файле с помощью R

Question

Я пытаюсь фильтровать перекрывающиеся строки в большом файле с R. Степени перекрытия задаются как 25%. Другими словами, число элементов пересечения между любыми двумя строками меньше, чем 0,25 раз их объединения. Если более 0,25, одна строка удаляется. Поэтому, если у меня есть большой файл с 1000 000 строк, первый 5 строк являются следующие:

с6 C24 C32 C54 C67
с6 C24 C32 C51 C68 C78
с6 C32 C54 C67
с6 C32 C55 C63 C85 C94 C75
с6 C32 C53 C67

Поскольку количество элементов пересечения между 1-й строкой и 2-й строкой 3 (например, c6, c24, c32), число соединений между ними равно 8 (например, c6, c24, c32, c54, c67, c51, c68, c78) , 3/8 = 0,375> 0,25, вторая строка удалена. Также выполните 3-й и 5-й ряды. Окончательный ответ - 1-я и 4-я строки.

с6 C24 C32 C54 C67
с6 C32 C55 C63 C85 C94 C75

код псевдо следующим образом:

for i=1:(n-1) # n is the number of rows of a file 
    for j=(i+1):n 
     if overlap degrees of the ith row and jth row is more than 0.25 
      delete the jth row from the file 
     end 
    end 

конец

Анализатор R код следующим образом:

con<-file("inputfile.txt","r") 
    fileConn<-file("outputfile025.txt") 
    data<-readLines(con,n=1) 
    con1<-strsplit(data,"\t") 
    writeLines(con1[[1]][], fileConn) 

    for(i in 2:1000000){ 
    data<-readLines(con,n=1) 
    con2<-strsplit(data,"\t") 

    intersect=length(intersect(con1[[1]][],con2[[1]][])) 
    union =length(union(con1[[1]][],con2[[1]][])) 

    if ((intersect/union)<0.25){ 
    writeLines(con2[[1]][], fileConn) 
    } 

    } 
    close(con) 
    close(fileConn) 

Проблема заключается в том, что приведенный выше код может быть использован только для фильтрации перекрытия между 1-й строкой и любыми другими строками, как фильтровать перекрытие между 2-м, 3, ...... строки и любые другие строки. Кто-нибудь знает, как решить эту проблему? Спасибо!

Answer 1

Здесь решение с использованием agrep, что приблизительные совпадений шаблона (здесь один элементом из вашего списка) в других элементах списка с помощью обобщенного Левенштейн редактирования расстояния:

max.distance=list(deletions=0.25) 

Так перекручивание через ваши данные с помощью lapply для пример:

res <- unlist(lapply(seq_along(ll),function(x){ 
    res <- agrep(pattern=ll[x],   # for each string 
       ll[-x],    # I search between the others strings 
       value=FALSE,max=list(deletions=0.25)) # I set the Levenshtein distance 
    if(length(res)==0) NA else res 
})) 
ll[res[!is.na(res) & duplicated(res)]] 

"c6 c24 c32 c54 c67"   
"c6 c32 c54 c67"    
"c6 c32 c55 c63 c85 c94 c75" 

Затем вы можете удалить дублированные и отсутствующие значения:

PS: здесь ll является:

ll <- readLines(textConnection(object='c6 c24 c32 c54 c67 
c6 c24 c32 c51 c68 c78 
c6 c32 c54 c67 
c6 c32 c55 c63 c85 c94 c75 
c6 c32 c53 c67'))