Найти подстроку в строке, используя процессы - PullRequest
Новая
       36

Найти подстроку в строке, используя процессы

0 голосов
/ 01 марта 2019

У меня есть большой файл (около 1 000 000 символов) в формате «AATACGTAGCTA» и последующий файл, например «CGTATC» (10 240 символов).Я хочу найти наибольшее совпадение подпоследовательности в основной последовательности.Полного 100% совпадения подпоследовательности может не существовать, это не гарантируется.В качестве небольшого примера вышеприведенное приведёт к выводу: Longest match is 4/6 starting at position 5.

Я работаю над основами C и хотел бы реализовать это так:

  • Пользователь выбирает, на сколько процессов он хотел бы разделить работу.
  • Каждый процесс выполняет 1 / n-ю часть работы и обновляет значения общей памяти, расположенные в struct.
  • Самый длинныйСоответствие (это могут быть не все символы) отражается в struct, а также в его начальной позиции и количестве совпадений.Смотрите вывод ниже.

Код 

#define _GNU_SOURCE
#include <limits.h>
#include <stdio.h>
#include <errno.h>
#include <semaphore.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/wait.h>
#include <fcntl.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <sys/types.h>
#include <sys/shm.h>

typedef struct memoryNeeded {
    int start_pos, total_correct;
    char sequence[1038336];
    char subsequence[10240];
    sem_t *sem;
} memoryNeeded;

// Used to check all arguments for validity
int checkArguments(char* p, int argc) {
    char *prcs;
    errno = 0;
    int num;
    long conv = strtol(p, &prcs, 10);

    if (errno!= 0 || *prcs != '\0' || conv > INT_MAX || conv > 50) {
        puts("Please input a valid integer for number of processes. (1-50)");
        exit(1);
    } else {
        num = conv;
        if (argc != 4) {
            puts("\nPlease input the correct amount of command line arguments (4) in"
                    "the format: \n./DNA (processes) (sequence) (subsequence)\n");
            exit(1);
        } else
            printf("Looking for string using %d processes...\n", num);

        return(num);
    }

}

int main (int argc, char* argv[]) {
    int processes = checkArguments(argv[1], argc);
    key_t shmkey;
    int procNumber, shmid, pid;
    FILE *sequence;
    FILE *subsequence;
    char *buf1, *buf2;

// Create shared memory
    size_t region_size = sizeof(memoryNeeded);
    shmkey = ftok("ckozeny", 5);
    shmid = shmget(shmkey, region_size, 0644 | IPC_CREAT);

    if (shmid < 0) {
        perror("shmget\n");
        exit(1);
    }

// Create structure in shared memory, attach memory and open semaphore
    memoryNeeded *mn;
    mn = (memoryNeeded *)shmat(shmid, NULL, 0);
    mn->sem = sem_open("sem", O_CREAT | O_EXCL, 0644, 1);

    sequence = fopen(argv[2], "r");
    subsequence = fopen(argv[3], "r");

// Get file sizes   
    fseek(sequence, 0L, SEEK_END);
    int sz1 = ftell(sequence);
    rewind(sequence);

    fseek(subsequence, 0L, SEEK_END);
    int sz2 = ftell(subsequence);
    rewind(subsequence);

// Read files into 2 buffers, which are put into struct mn   
    buf1 = malloc(sz1);
    buf2 = malloc(sz2);

    if (sz1 != fread(buf1, 1, sz1, sequence)) {
        free(buf1);
    }
    if (sz2 != fread(buf2, 1, sz2, subsequence)) {
        free(buf2);
    }

// Initialize struct with necessary values
    mn->start_pos = 0;
    mn->total_correct = 0;
    strncpy(mn->sequence, buf1, sz1);
    strncpy(mn->subsequence, buf2, sz2);

    fclose(sequence);
    fclose(subsequence);

// Begin n forks    
    for (procNumber = 0; procNumber < processes; procNumber++) {

        pid = fork();

        if (pid < 0) {
            sem_unlink("sem");
            sem_close(mn->sem);
            printf ("Fork error.\n");
        } else if (pid == 0)
            break;
    }

    if (pid != 0) {
        while ((pid = waitpid (-1, NULL, 0))){
            if (errno == ECHILD)
                break;
        }

        printf("Best match is at position %d with %d/10240 correct.", mn->start_pos, mn->total_correct);
        printf ("\nParent: All children have exited.\n");

        sem_unlink("sem");
        sem_close(mn->sem);
        shmdt(mn);
        shmctl(shmid, IPC_RMID, 0);
        exit(0);
    } else {
// this child process will do its 1/nth of the work
        sem_wait(mn->sem);

        printf ("Child(%d) is in critical section.\n", procNumber);
        sleep(1);

        int i = 0;
        int longest, count = 0;
        for (i = 0; i < sz1; i += processes) {
            for (int j = 0; j < sz2; j += processes) {
                count = 0;
                while (mn->sequence[i+j] == mn->subsequence[j]) {
                    count++;
                    j++;
                }
                if (count > longest) {
                    longest = count;
                }
            }
        }

// If local match is longer than that of the struct, update and unlock      
        if (longest > mn->total_correct) {
            mn->total_correct = count;
            mn->start_pos = (i - count);
            sem_post(mn->sem);
        } else
// If not - unlock and let next process go                
            sem_post(mn->sem);

        exit(0);
    }
    return 1;
}

  • Текущий дочерний код является более или менее "псевдокодом".Я собрал это вместе, как это имеет смысл в моей голове.(Я знаю, что это может быть неправильно или работать не так, как задумано.) Мой вопрос касается алгоритма дочернего кода в нижней части.

  • Как мне реализовать это, чтобы каждый ребенок выполнял 1 / n-ю часть работы и находил самое длинное совпадение, даже если оно не соответствует 100%?

  • Окончательный результат будет:
    ./DNA 6 sequence1 subsequence1 Looking for string using 6 processes... Best match is at position 123456 with 9876/10240 correct.

Спасибо.

...