목록에 저장된 300K 문자열이 있고 각 문자열의 길이는 10-400입니다. 다른 문자열의 하위 문자열 인 문자열을 제거하고 싶습니다. 길이가 짧은 문자열은 다른 사람의 부분 문자열이되어야 함).문자열 일치가 파이썬
현재 길이에 따라이 300K 문자열을 정렬 한 후 아래 방법을 사용합니다.
sorted_string = sorted(string_list, key=length, reverse=True)
for item in sorted_string
for next_item in sorted_string[sorted_string.index(item)+1:]
if next_item in item:
del sorted_string[sorted_string.index(next_item)]
이 메서드의 실행 시간은 O (n^2)입니다. 300K 문자열이 있으므로이 방법에 만족하지 않습니다.
이러한 정렬 된 문자열을 다른 청크로 나누고 다중 처리를 사용하여 각 청크를 계산하려고했습니다. 첫 번째 생각은 첫 번째 청크에 첫 번째 10K를 넣고 두 번째 청크에 다음 10K를 넣는 것입니다.하지만이 방법으로 각 청크의 문자열 길이는 비슷하며 같은 청크에서 다른 문자열을 부분 문자열로 만들지 않을 수 있습니다. 따라서 이것은 좋은 분열 전략이 아닙니다.
좋은 아이디어가 있습니까?
편집는 이러한 문자열은 DNA 서열을 나타내며, 단지 'g', 'C', 't'와 'A'
업데이트가 포함
나는를 구축하는 시도 접미사 트리 https://github.com/kvh/Python-Suffix-Tree에서 코드를 사용하여. 이 프로그램은 Ukkonen's algorithm을 기반으로 접미어 트리를 만듭니다.
연결 문자열의 총 길이는 약 90,000,000입니다. 그것은 많은 수입니다. 이 프로그램은 30 분 동안 진행되었으며 ~ 300 만 (1/30) 문자 만 처리됩니다. 나는이 프로그램에 만족하지 않는다.
이 큰 문자열을 처리 할 수있는 다른 접미사 트리 작성 알고리즘이 있습니까?
다른 문자열의 부분 문자열 인 찾을 문자열의 수는 얼마입니까? 그게 가장 효과가있는 것에 영향을 미칠 수도 있습니다 –
또한,이 문자열의 본질은 무엇입니까? 그들은 문장입니까? 그렇다면 어떤 언어입니까? 그들은 단지 임의의 캐릭터입니까? 그것들은 DNA의 표현이며 그래서 'g', 't', 'c', 'a'만을 포함 할 것인가? –
@RobWatts 예, DNA 서열이며 'g' 'c' 't' 'a'만 포함합니다. 그리고 얼마나 많은 문자열이 부분 문자열이 될지 전혀 알지 못합니다. – mitchelllc