여러 단어에서 서로 다른 동일한 문자를 필터링합니다.

파일 목록을 여러 번 처리하는 것을 피하기는 어렵지만 각 규칙을 한 번만 처리하면 충분합니다. 주요 프로세스는 가능한 "단어 목록"을 확장하면서 단어를 10번 반복하는 것입니다. 여기서 각 목록에 대해 i:번째 단어는 해당 목록의 i:번째 규칙과 일치합니다. 각 단어가 목록과 일치하면 해당 단어가 추가되어 목록이 확장됩니다.

bash:R이 데이터 구조를 유지하기에는 다소 약하지만 선택적으로 "단어 목록"을 확장된 목록에 적용할 다음 규칙을 나타내는 쉼표로 구분된 단어 시퀀스로 나타낼 수 있습니다 . R이는 R물론 목록의 단어 수에 1을 더한 것과 같습니다. 이를 기본 데이터 구조로 사용하면 다음과 같은 기본 프로세스가 나타날 수 있습니다.

N=0
M=0
cat $1 $1 $1 $1 $1 $1 $1 $1 $1 $1 | while read w || ending ; do
    [ -z "$F" ] && F=$w # capture the first word                                
    [ "$F" = "$w" ] && N=$((N+1)) # count first word appearances                
    Q=( )
    matches $w 1 "" && Q=( ${w}:2 )
    for p in ${P[@]} ; do
        A="${Q[@]}" && [ "${A/$p/}" = "${A}" ] || continue # if duplicate       
        R=${p#*:} && [ $R -lt $M ] && continue # if path too short              
        Q=( ${Q[@]} $p ) # preserve this path for next word                     
        [ "${p/$w/}" = "$p" ] || continue # if word already in path             
        p=${p%:*} # p is now the word list only                                 
        if matches $w $R $p ; then
            Q=( ${Q[@]} $p,${w}:$((R+1)) )
            M=$N
        fi
    done
    P=( ${Q[@]} )
done

이 기능은 단어가 규칙 목록의 적절한 확장 matches인지 여부를 결정하기 위한 규칙의 조작적 표현입니다 . w다음과 같은 것(메인 프로그램 앞에 위치):pR

matches() {
    local w=$1
    local p=$3
    case $2 in
        1) # -112--3---
            eqchar $w 2 $w 3
            ;;
        2) # ---2--3-4-
            eqchar $w 4 $p 4 && eqchar $w 7 $p 7
            ;;
        3) # -5-2----4-
            eqchar $w 4 $p 4 && eqchar $w 9 $p $((11+9))
            ;;
        4) # -5-2--6-4-
            eqchar $w 2 $p $((22+2)) && eqchar $w 4 $p 4 &&
              eqchar $w 9 $p $((11+9))
            ;;
        5) # 75-2--6---
            eqchar $w 2 $p $((22+2)) && eqchar $w 4 $p 4 &&
              eqchar $w 7 $p $((11+7))
        ;;
        6) # 6: 75---8----
            eqchar $w 1 $p $((44+1)) && eqchar $w 2 $p $((22+2)) &&
              eqchar $w 7 $p $((33+7))
            ;;
        7) # 7: 7----8----
            eqchar $w 1 $p $((44+1)) && eqchar $w 6 $p $((55+6))
            ;;
        8) # 8: 79---8----
            eqchar $w 1 $p $((44+1)) && eqchar $w 6 $p $((55+6))
            ;;
        9) # 9: -9--0-----
            eqchar $w 2 $p $((77+2))
            ;;
        10) # 10: -9--0---xx
            eqchar $w 2 $p $((77+2)) && eqchar $w 5 $p $((88+5)) &&
              [ -z "${1#*xx}" ]
            ;;
        *)
            return 1
            ;;
    esac
}

이 eqchar함수는 단순히 주어진 위치에 있는 첫 번째 문자열의 문자가 특정 위치에 있는 두 번째 문자열의 문자와 일치하는지 여부를 테스트합니다. 후자의 문자열은 쉼표로 구분된 순서의 선행 단어이므로 i*11+jj:번째 문자(1 기반)에서 i:번째 단어(0 기반)에 대한 인덱싱 방식을 허용합니다. 예를 들어 색인은 $((77+2))8번째 단어의 두 번째 문자입니다.

eqchar() {
    local w=$1
    local p=$3
    [ "${w:$(($2-1)):1}" = "${p:$(($4-1)):1}" ]
}

함수는 함수 이전에 선언되어야 eqchar하며 , 반드시 기본 프로시저보다 먼저 선언되어야 합니다.matches

마지막으로, 메인 프로그램에는 ending마지막에 결과를 인쇄하는 기능이 포함되어 있습니다. 예상되는 결과는 P길이가 10인 "단어 목록"을 저장하는 것이지만 일반적으로 P규칙에 맞는 matches가능한 가장 긴 단어 목록은 실제로 모두 저장됩니다. 함수 ending는 필요한 인쇄물을 생성한 다음 반환하여 절 1을 종료해야 합니다 while.

이는 O(N)(또는 O(N*T), 여기서 T는 매우 높을 경우 첫 번째 규칙과 일치하는 수)를 사용하는 "순수한" bash 솔루션입니다.

샘플 텍스트를 사용하여 워드 파일을 만들었습니다.

-bash-4.2$ cat words
aaadiigjlf
abcdefghij
aswdofflle
bbbbbbbbbb
bisofmlwpa
fsbdfopkld
gikfkwpspa
hogkellgis

스크립트는 매번 첫 번째 단어를 설정하는 단어 목록을 반복한 다음 단어 파일의 내용을 반복하여 4번째와 7번째 문자를 비교합니다. 일치하는 항목을 찾으면 일치 항목을 두 번째 단어로 설정하고 지금까지의 솔루션을 에코합니다. 스크립트는 템플릿이므로 후속 중첩 루프에 각각의 추가 제약 조건을 추가해야 합니다.

-bash-4.2$ cat script
#!/bin/bash

for worda in $(cat ./words ); do
        firstword=$worda
        for wordb in $(cat ./words | grep -v $firstword); do
                if [ $(echo $firstword | cut -c 4,7) = $(echo $wordb | cut -c 4,7) ]; then
                        secondword=$wordb
                        echo "$firstword  $secondword"
                fi
        done
done

다음은 스크립트의 출력입니다.

bash-4.2$ ./script
aaadiigjlf  abcdefghij
abcdefghij  aaadiigjlf

팁: 4,7의 두 발생을 4,9로 변경하고 이것이 출력에 어떤 영향을 미치는지 확인하십시오. 추가 for 루프를 중첩해 볼 수 있습니다.

나는 당신을 위해 모든 것을 해주고 싶지는 않지만 (숙제처럼 보이기 때문에) 당신을 올바른 길로 인도하는 데는 충분할 것입니다. 제가 제공한 내용을 사용하여 여기에서 수동으로 이 작업을 수행하고 각 제약 조건을 비교에 삽입할 수 있습니다.