Отображение списка ребер с метками строковых узлов на целочисленные метки - PullRequest
Новая
       11

Отображение списка ребер с метками строковых узлов на целочисленные метки

1 голос
/ 10 мая 2019

У меня есть огромный граф в формате списка краев со строками в качестве меток узлов.Интересно, каков «лучший» способ сопоставить строки с целыми числами.Входной файл следует примеру: 

Mike Andrew
Mike Jane
John Jane

Вывод (т. Е. Сопоставленный файл) должен быть: 

1 2
1 3
4 3

Вставлен ниже скелет в C, который читает входной файл.Может кто-нибудь, пожалуйста, посоветуйте мне, как действовать. 

#include <stdio.h>

int LoadFile(const char * filename) {
  FILE *fp = NULL;
  char node1[10];
  char node2[10];
  int idx = 0;

  fp = fopen(filename, "r");
  if (fp == NULL) {
    perror("Error");
  }

  while (fscanf(fp, "%s %s", &node1, &node2) == 2) {
    idx++;
  }

  fclose(fp);

  return idx;
}

int main(void) {
  int n = LoadFile("./test.txt");
  printf("Number of edges: %d\n", n);
  return 0;
}

Ответы [ 2 ]

2 голосов
/ 10 мая 2019

Вам необходимо иметь наивную реализацию карты (отображающую строки в целые числа) .

  • Определить структуру, как показано ниже, для хранения строк. 

        typedef struct {
       unsigned int hashed;
       char **map;
   } hash;

  • Определите функцию, которая будет вставлять строку в hashmap, если она не существует, и возвращать индекс строки в hashmap.

    int insertInMap(hash *map, char *entry)

  • Сохранение возвращенного индекса в структуре edge.

    edges[i].first =insertInMap(&map,first_string); edges[i].second =insertInMap(&map,second_string)

Пример кода: 

typedef struct {
    unsigned int first;
    unsigned int second;
} edge;

typedef struct {
    unsigned int hashed;
     char **map;
} hash;


int insertInMap(hash *map, char *entry)
{
  int i =0;
  for (i=0;i<map->hashed;i++)
  {
    if (strcmp(map->map[i],entry) == 0)
    return i+1;
  }
  /* Warning no boundary check is added */
  map->map[map->hashed++] = strdup(entry);   
  return map->hashed;
}


edge *LoadFile(const char * filename) {
  FILE *fp = NULL;
  char node1[10];
  char node2[10];
  int idx = 0;

  edge *edges;
  hash map;    

  int numEdges = 10;
  edges = malloc( numEdges * sizeof(edge));

  map.map = malloc(numEdges * sizeof(char*));
  map.hashed = 0;

  fp = fopen(filename, "r");
  if (fp == NULL) {
    perror("Error");
  }

  while (fscanf(fp, "%s %s", &node1, &node2) == 2) {
    if (idx >= numEdges)
    {
         numEdges *=2;
         edges = realloc(edges, numEdges * sizeof(edge));

         map.map = realloc(map.map, numEdges * sizeof(char*));
    }
    edges[idx].first =insertInMap(&map,node1);
    edges[idx].second =insertInMap(&map,node2);
    idx++;
  }

  fclose(fp);

  return edges;
}

Позже выведите edges.

1 голос
/ 10 мая 2019

Я бы предложил использовать структуру данных Trie .Он предназначен для хранения слов и сопоставления их значения.

Преимущества дерева по сравнению с хэш-картой следующие:

  • Поиск элемента быстрее
  • Нет столкновений
  • Простые способыпройти через три или вернуть все значения в алфавитном порядке
  • Простая реализация (без хэш-функции, без связанных списков ...).Это простое дерево.

Обычно использование памяти в трие меньше, чем в хэш-таблице, но в худшем случае оно будет использовать больше памяти.

Еще более эффективноструктура данных для этой цели - DAWG (или детерминированный ациклический конечный автомат), но его построение гораздо сложнее, поэтому, если у вас нет миллионов узлов в вашем графике, я бы предложил вам придерживатьсяTrie.

Возможная реализация в C будет выглядеть следующим образом: Структура данных: 

#include <stdlib.h>
#include <stdio.h>

#define ALPHABET_SIZE 26
#define IMPOSSIBLE_VALUE -42

typedef struct TrieNode_struct {
    struct TrieNode_struct *children[ALPHABET_SIZE];
    int value;
} TrieNode_t;

typedef TrieNode_t *Trie_t;


TrieNode_t *new_node() {
    TrieNode_t *new_node = malloc(sizeof(TrieNode_t));
    new_node->value = IMPOSSIBLE_VALUE;
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        new_node->children[i] = NULL;
    }
    return new_node;
}

int char_to_idx(char c){
    return c - 'a';
}

Вставить пару строка / значение в три 

void trie_insert_rec(TrieNode_t *node, char *str, int val, int depth) {
    if (str[depth] == '\0') {
        node->value = val;
    } else {
        if (node->children[char_to_idx(str[depth])] == NULL) {
            node->children[char_to_idx(str[depth])] = new_node();
        }
        trie_insert_rec(node->children[char_to_idx(str[depth])], str, val, depth+1);
    }
}

void trie_insert(Trie_t trie, char *str, int val) {
    trie_insert_rec(trie, str, val, 0);
}

Поискдля значения в поле: 

int trie_fetch_rec(TrieNode_t *node, char *str, int depth) {
    if (str[depth] == '\0') {
        return node->value;
    } else if (node->children[char_to_idx(str[depth])] == NULL) {
        return IMPOSSIBLE_VALUE;
    } else {
        return trie_fetch_rec(node->children[char_to_idx(str[depth])], str, depth+1);
    }
}

int trie_fetch(TrieNode_t *node, char *str){
    return trie_fetch_rec(node, str, 0);
}

Крошечный игрушечный тест 

int main() {
    Trie_t trie = new_node();
    char str[5] = "john\0";
    trie_insert(trie, str, 11);
    printf("%d\n", trie_fetch(trie, str));
}
...