여러 일반 시작 문자열 찾기

Question

하나 이상의 문자열 하위 집합에 공통 시작 문자열이있는 문자열 목록이 있습니다. 문자열의 원래 목록을 입력으로 받아 모든 일반적인 시작 문자열 목록을 반환하는 함수를 원합니다. 필자의 경우에는 각 공통 접두어가 주어진 구분 기호로 끝나야한다는 것을 알고 있습니다. 다음은 내가 얘기하고 입력 데이터의 유형의 예 (색상 강조를 무시)입니다 :

는

Population of metro area/Portland 
Population of city/Portland 
Population of metro area/San Francisco 
Population of city/San Francisco 
Population of metro area/Seattle 
Population of city/Seattle 

여기에 구분 기호는 /하고 일반적인 시작 문자열은 Population of metro area 및 Population of city이다. 아마도 분리 문자는 궁극적으로는 중요하지 않겠지 만 한 가지 결과가 돌아 오는 것을 원하지 않는다는 것을 강조하기 위해 삽입했습니다. 즉 보편적 인 공통 시작 문자열 Population of; 공통 부분 문자열 Population of metro area/S 및 Population of city/S도 필요하지 않습니다.

이 알고리즘의 궁극적 인 사용법은 공통 접두어로 문자열을 그룹화하는 것입니다. 예를 들어, 위의 목록과 같이, 중복 정보를 제거하는 계층 구조로 재구성 될 수있다 : 나는 어떤 언어로 파이썬하지만 의사 코드를 사용하고

Population of metro area 
    Portland 
    San Francisco 
    Seattle 
Population of city 
    Portland 
    San Francisco 
    Seattle 

잘 될 것입니다.

EDIT 톰 앤더슨 바와 같이, 주어진 원래의 문제가 쉽게 간단히 스트링을 분할 및 접두어 그룹 해시를 사용하여 감소 될 수있다. 원래 문제가 더 복잡 할 수 있다고 생각 했었습니다. 때로는 실제로 구분 기호가 삽입 된 접두사가 있기 때문에 한 번만 분할하는 것만으로도 올바른 분할을 수행 할 수 있기 때문에 해결할 수 있습니다.

Answer 1

문자열을 반복하면서 구분 기호로 분리 한 다음 두 번째 반쪽을 첫 번째 반쪽으로 그룹화하지 않습니까? 그래서 같이 : 당신이 문자열 prefices을 찾는 경우 일반적으로

def groupByPrefix(strings): 
    stringsByPrefix = {} 
    for string in strings: 
      prefix, suffix = map(str.strip, string.split("/", 1)) 
      group = stringsByPrefix.setdefault(prefix, []) 
      group.append(suffix) 
    return stringsByPrefix 

,이 솔루션은 trie로 문자열을 때려 눕히다하는 것입니다. 여러 하위 노드가있는 분기 노드는 최대 공통 접두사입니다. 그러나 당신의 필요는 그것보다 더 제한되어 있습니다. 당신이 당신의 텍스트 주위에 여분의 공백이 없습니다 알고 있다면 당신은 line.split('/')에 의해 (i.strip() for i in line.split('/')를 대체 할 수

{'Population of city': 
     ['Portland', 
     'San Francisco', 
     'Seattle'], 
'Population of metro area': 
     ['Portland', 
     'San Francisco', 
     'Seattle']} 

---

하십시오 딕셔너리처럼

Answer 2

d = collections.defaultdict(list) 

for place, name in ((i.strip() for i in line.split('/')) 
        for line in text.splitlines()): 
    d[place].append(name) 

그렇게 d이 될 것입니다.

Answer 3

이 매우 일반적 아니라, 당신이 필요로하는 일을 할 수

def commons(strings): 
    return set(s.split('/')[0] for s in strings) 

을 그리고 그룹에 대한 데이터를 통해 다시 피하려고

def group(strings): 
    groups = {} 
    for s in strings: 
     prefix, remainder = s.split('/', 1) 
     groups.setdefault(prefix, []).append(remainder) 
    return groups 

Answer 4

csv.reader 및 itertools.groupby을 사용하여 치료 첫 번째 열의 구분 기호와 그룹으로 '/'를 사용하십시오.

for key, group in groupby(sorted(reader(inp, delimiter='/')), key=lambda x: x[0]): 
    print key 
    for line in group: 
     print "\t", line[1]