Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/9: Рейтинг темы: голосов - 9, средняя оценка - 5.00
СyberSpec
Кибернетик
462 / 86 / 12
Регистрация: 10.04.2009
Сообщений: 424
1

Алгоритм поиска ошибки.

11.05.2011, 21:13. Просмотров 1640. Ответов 9
Метки нет (Все метки)

Приветствую.

Нужна помощь в составлении алгоритма поиска ошибки в таблице.
Ломаю голову, пока ничего интересного не придумал.
Суть вопроса в этой теме: Выборка ошибочных данных, возможна?
Предлагаю продолжить здесь, так как тут больше вопрос алгоритма, а не реализации.

Если есть идеи/вопросы буду рад услышать.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.05.2011, 21:13
Ответы с готовыми решениями:

алгоритм поиска
помогите пожалуйста выбрать правильный ответ в алгоритме. Это тестовая задачка Для построения...

Алгоритм поиска
Привет всем.Вот тут задумался над алгоритмом поиска,смотрите я придумал такую схему:краулер обходит...

Алгоритм поиска совпадений
Всем привет! Я веб-программист. Хочу сделать доброе дело, написать один микро-сервис. Идея...

Алгоритм поиска алгоритма
Здравствуйте! Хочу написать программу которая будет искать алгоритм который связывает числа....

Алгоритм поиска путей
Привет. Ребята, такая тема, у меня есть граф, взвешенный, неориентированный, у меня есть пути из...

9
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
11.05.2011, 21:24 2
Цитата Сообщение от СyberSpec Посмотреть сообщение
Ошибочна она потому, что есть строки (2 или больше) с точно такими же данными, но есть отличие в 1м символе.
Получается, вторая и третья строка также являются ошибочными, для них это условие тоже выполняется. Это нормально?
0
СyberSpec
Кибернетик
462 / 86 / 12
Регистрация: 10.04.2009
Сообщений: 424
11.05.2011, 21:37  [ТС] 3
Имеется таблица:
-----------------------------------------------
ONUM | AMT | ODATE | CNUM | SNUM
-------|------|-------------|------|------
3001 | 18.69 | 10/03/1990 | 2008 | 1007
3003 | 767.19 | 10/03/1990 | 2001 | 1001
3003 | 767.19 | 10/03/1990 | 2001 | 1001

3013 | 767.19 | 10/03/1990 | 2001 | 1001
3010 | 1309.95 | 10/06/1990 | 2004 | 1002
3011 | 9891.88 | 10/06/1990 | 2006 | 1001
-----------------------------------------------

ошибочна только строка выделенная жирным шрифтом. 2 и 3 строки курсивом - правильные так как они полностью совпадают. совпадают они и с жирной строкой, отличие только в 1м символе 3013 вместо 3003. Вот, что имел ввиду.
0
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
11.05.2011, 21:54 4
А если будет еще одна строка
3013 | 767.19 | 10/03/1990 | 2001 | 1001
кто тогда будет ошибочным?
0
СyberSpec
Кибернетик
462 / 86 / 12
Регистрация: 10.04.2009
Сообщений: 424
11.05.2011, 21:56  [ТС] 5
Цитата Сообщение от Хохол Посмотреть сообщение
А если будет еще одна строка
3013 | 767.19 | 10/03/1990 | 2001 | 1001
кто тогда будет ошибочным?
тогда ошибок нет. если строк 2 то, считаем, что все ок.
0
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
11.05.2011, 22:00 6
Напишите четко, какая строка считается ошибочной.
0
СyberSpec
Кибернетик
462 / 86 / 12
Регистрация: 10.04.2009
Сообщений: 424
11.05.2011, 22:07  [ТС] 7
Цитата Сообщение от Хохол Посмотреть сообщение
Напишите четко, какая строка считается ошибочной.
Строка считается ошибочной если есть две такие же строки(или более), но с отличием в 1 символ.
пример:
строка1 "1234567890"
строка2 "1234567890"
строка3 "1234667890" // ошибочна, потому что есть строка1 и строка2 (они совпадают), и строка3 отличается от них одним и тем же символом.
0
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
11.05.2011, 22:10 8
ууу.
Если это четкое определение, то это откуда?
Цитата Сообщение от СyberSpec Посмотреть сообщение
тогда ошибок нет. если строк 2 то, считаем, что все ок.
0
СyberSpec
Кибернетик
462 / 86 / 12
Регистрация: 10.04.2009
Сообщений: 424
12.05.2011, 08:18  [ТС] 9
Строка считается ошибочной если:
1) есть две или более такие же строки, но с отличием в один и тот же символ.
2) точно такой же строки как эта (ошибочная) нет.

Если по другому сказать, нужно найти уникальную строку, отличающуюся от других, двух и более строк, одним и тем же символом.

Вот.
0
СyberSpec
Кибернетик
462 / 86 / 12
Регистрация: 10.04.2009
Сообщений: 424
21.09.2011, 08:04  [ТС] 10
Решение найдено. В моем случае алгоритм будет таким.
Алгоритм поиска и замены опечаток в текстовых полях таблицы (Пример с полем "Фамилия"):
  1. Получаем список уникальных строк-эталонов. (я беру из другой таблицы, где есть эти же данные) вида:
    ФамилияИмяОтчествоГод. рожд.
  2. Берем 1-ю строку-эталон и делаем селект вида:
    T-SQL
    1
    
    Select [familiya] From [bad_table] Where [Name] = 'etalon_name' And [Otchestvo] = 'etalon_otchestvo' And [GodRogdeniya] = 'etalon_godrogdeniya'
  3. Из полученной выборки таблицы [bad_table] последовательно сравниваем значения [familiya] с строкой-эталоном по алгоритму "Расстояние Дамерау-Левенштейна", и если значения отличаются в 1 символ, то делаем Update этой записи.
  4. Сам алгоритм лучше реализовать в программе и переложить на нее обязанности вычисления, ибо записей много а сервер один
Описание алгоритма есть в википедии, а реализация на C# вот:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public static Int32 DamerauLevenshteinDistance(String source, String target)
{
    if (String.IsNullOrEmpty(source))
    {
        if (String.IsNullOrEmpty(target))
        {
            return 0;
        }
        else
        {
            return target.Length;
        }
    }
    else if (String.IsNullOrEmpty(target))
    {
        return source.Length;
    } 
 
    Int32 m = source.Length;
    Int32 n = target.Length;
    Int32[,] H = new Int32[m + 2, n + 2];
 
    Int32 INF = m + n;
    H[0, 0] = INF;
    for (Int32 i = 0; i <= m; i++) { H[i + 1, 1] = i; H[i + 1, 0] = INF; }
    for (Int32 j = 0; j <= n; j++) { H[1, j + 1] = j; H[0, j + 1] = INF; }
 
    SortedDictionary<Char, Int32> sd = new SortedDictionary<Char, Int32>();
    foreach (Char Letter in (source + target))
    {
        if (!sd.ContainsKey(Letter))
            sd.Add(Letter, 0);
    }
 
    for (Int32 i = 1; i <= m; i++)
    {
        Int32 DB = 0;
        for (Int32 j = 1; j <= n; j++)
        {
            Int32 i1 = sd[target[j - 1]];
            Int32 j1 = DB;
 
            if (source[i - 1] == target[j - 1])
            {
                H[i + 1, j + 1] = H[i, j];
                DB = j;
            }
            else
            {
                H[i + 1, j + 1] = Math.Min(H[i, j], Math.Min(H[i + 1, j], H[i, j + 1])) + 1;
            }
 
            H[i + 1, j + 1] = Math.Min(H[i + 1, j + 1], H[i1, j1] + (i - i1 - 1) + 1 + (j - j1 - 1));
        }
 
        sd[source[i - 1]] = i;
    }
 
    return H[m + 1, n + 1];
}
0
21.09.2011, 08:04
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.09.2011, 08:04

Алгоритм поиска информации
ПОИСК И ХРАНЕНИЕ ИНФОРМАЦИИ В СПРАВОЧНИКАХ Цель: Изучение основных принципов построения...

Алгоритм поиска перестановок
помогите написать алгоритм поиска перестановок в числе, но не простой, а чтобы были перестановки по...

Алгоритм поиска VBA
История классическая - задали задачу и после 3 часов медитирования над ней результат = 0. Буду...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru