텍스트를 파싱하고 유사점을 반환하십시오.

Question

여러 개의 URL이 있고 각각의 URL에서 기본 이름을 반환한다고 가정 해 봅시다.

http://www.test.com/the.code.r00 

반환

the.code.r00 

나는 내가 다른 URL을

에서 너무 다음 basename이있는 사람들과

the.code.r00 
the.code.r01 
.. 
... 
the.code.r12 

와 함께 작업하기 위해 여러 URL을 추출 여러 basename이 있습니다

the.matrix.r00 
the.matrix.r01 
.. 
... 
the.matrix.r14 

내가 테스트하고 나는 위의 basename이 구문 분석 후

the.code.r 
the.matrix.r 

을 반환 입증되었습니다 알려진 알고리즘이 있는지 알고 싶습니다.

또한, 대신 * super Tools와 동일한 기능을 수행하는 * nix 도구가 있습니다.

형식이 항상 위와 같지는 않습니다. 그렇지 않으면 간단한 substr을 수행 할 수 있습니다. 숫자는 항상 문자열의 특정 위치에 나열되지는 않습니다. 몇 가지 다른 예;

the.code.part01.rar 
the.code.001 
.. 
.... 

.. 나는이 작업을 수행하는 내 자신의 알고리즘을 구현할 수 있지만, 이미 정의가있는 경우 알려진 알고리즘을 사용하는 것을 선호 것, 그래서 그것은 아마 무거운 테스트없이 버그의 수있을 것

Answer 1

아마도 longest common substring problem의 고정 된 구현을 찾고있을 것입니다. 문자열 목록을 정렬하고 인접 요소에 고정 된 LCS를 수행하십시오. LCS를 키로 사용하고 두 문자열을 값으로 사용하여 다중 값 해시 맵에 LCS를 삽입하십시오.

일단 임계 값을 충족 할 때까지 LCS 문자열과 동일하게하십시오.

Answer 2

목록의 각 문자열 쌍을보고 Levenshtein Distance (일명 문자열 편집 거리)을 계산하십시오. 이렇게하면 한 문자열을 다른 문자열로 변경하는 데 필요한 최소 변경 횟수가 제공됩니다.

이제 Levenshtein 구현에서 동적 프로그램의 백 포인터를 따라 가면서 문자열 간의 실제 변경 집합을 가져옵니다. 변경 사항 세트가 다른 숫자로 대체되는 숫자로만 이루어진 경우 패턴을 발견했습니다. 문자열 중 하나를 복사하고 해당 숫자를 제거한 다음 패턴 세트에 저장하고 다른 문자열 쌍을 계속 사용하십시오.