Поиск:

Ответ в темуСоздание новой темы Создание опроса
> сравнение строк 
:(
    Опции темы
blackbanny
Дата 17.7.2013, 12:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 83
Регистрация: 18.11.2009

Репутация: нет
Всего: нет



Доброго времени суток!
Имеется список слов и некий получаемый текст. Нужно перебирать список слов и искать эти слова в получаемом тексте. Проблема в том, что получаемый текст может приходить с ошибками, например, в словаре есть такое слово "DEL'ESTANG", а в тексте только "'ESLANG". С помощью какого алгоритма можно с наибольшей долей вероятности определить, что слово "DEL'ESTANG" изначально было в тексте? Подойдет ли алгоритм расстояние Левенштейна или есть более эффективные алгоритмы? Может есть готовые легковесные библиотеки?

Добавлено через 7 минут и 48 секунд
или вот еще такой пример:
в словаре есть слово "BORDEAUX"
получаемый текст следующий ") R D E A UX CHATEAU l'Estang ■'IS DE CASTILLOS ot castilio*con 2 00 8 "
пробелы в получаемом тексте скорее всего нужно будет убрать(это делается просто стандартными функциями языка), а вот как действовать дальше? 
PM MAIL   Вверх
mrgloom
Дата 17.7.2013, 15:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 829
Регистрация: 8.6.2011

Репутация: нет
Всего: нет



кстати меня тоже интересует данный вопрос, я так понимаю тут разговор идёт об OCR.


вроде как есть какие то техники, которые позволяют сдетектировать фразу например из N букв, но во-первых мы можем иметь ошибки в определении самих букв, т.е. по правильному мы должны иметь лишь вероятность нахождения буквы на k-ой позиции, а потом перебирая все варианты должны получить "осмысленное" слово из словаря.

вообщем должна быть какая то вероятностная модель по идее. 
PM MAIL   Вверх
blackbanny
Дата 17.7.2013, 16:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 83
Регистрация: 18.11.2009

Репутация: нет
Всего: нет



Цитата(mrgloom @  17.7.2013,  15:07 Найти цитируемый пост)
тут разговор идёт об OCR

именно, а точнее о результате распознавания. с нем и нужно проводить манипуляции.
Цитата(mrgloom @  17.7.2013,  15:07 Найти цитируемый пост)
но во-первых мы можем иметь ошибки в определении самих букв

ну из-за ошибок в распознавании я и задал вопрос...
Цитата(mrgloom @  17.7.2013,  15:07 Найти цитируемый пост)
вероятность нахождения буквы на k-ой позиции

что-то проверять по позиции в моем случае не получится, потому что слова могут располагаться в разных частях текста...
PM MAIL   Вверх
Pavia
Дата 17.7.2013, 17:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 418
Регистрация: 6.12.2008

Репутация: 11
Всего: 12



Цитата(blackbanny @  17.7.2013,  12:41 Найти цитируемый пост)
Подойдет ли алгоритм расстояние Левенштейна или есть более эффективные алгоритмы?

Думаю с такими ошибками лучше всего справится Левенштейн. Можно попробовать собрать статистику ошибок и улучшить алгоритм, но сомневаюсь что это даст прирост более 1/1000.
Тут надо улучшать обработку перед OCR.
А так совет один трудитесь. Чем больше придумаете тем лучше будет.
PM MAIL   Вверх
mrgloom
Дата 18.7.2013, 08:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 829
Регистрация: 8.6.2011

Репутация: нет
Всего: нет



Цитата

что-то проверять по позиции в моем случае не получится, потому что слова могут располагаться в разных частях текста


ну тогда видимо пробегать по фразе словом из словаря и смотреть насколько совпадает.


PM MAIL   Вверх
blackbanny
Дата 18.7.2013, 16:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 83
Регистрация: 18.11.2009

Репутация: нет
Всего: нет



Цитата(mrgloom @  18.7.2013,  08:09 Найти цитируемый пост)
смотреть насколько совпадает.

с помощью какого алгоритма можно узнать насколько совпадает?
PM MAIL   Вверх
mrgloom
Дата 18.7.2013, 16:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 829
Регистрация: 8.6.2011

Репутация: нет
Всего: нет



по-моему это называется Approximate string matching
http://en.wikipedia.org/wiki/Approximate_string_matching

расстояние Левенштейна  это видимо один из методов.


PM MAIL   Вверх
Albor
Дата 18.7.2013, 21:20 (ссылка) |    (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 589
Регистрация: 28.2.2009

Репутация: нет
Всего: 9



Цитата(blackbanny @  18.7.2013,  15:37 Найти цитируемый пост)
с помощью какого алгоритма можно узнать насколько совпадает?

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

Это сообщение отредактировал(а) Albor - 19.7.2013, 07:18

Присоединённый файл ( Кол-во скачиваний: 3 )
Присоединённый файл  tesst.rar 96,12 Kb
PM MAIL ICQ   Вверх
blackbanny
Дата 19.7.2013, 06:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 83
Регистрация: 18.11.2009

Репутация: нет
Всего: нет



конечно интересно, было бы интересно посмотреть smile
PM MAIL   Вверх
Albor
Дата 19.7.2013, 07:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 589
Регистрация: 28.2.2009

Репутация: нет
Всего: 9



Цитата(blackbanny @  19.7.2013,  05:40 Найти цитируемый пост)
конечно интересно, было бы интересно посмотреть 

Присоединил к предыдущему сообщению, иначе почему-то не отправлялось.
PM MAIL ICQ   Вверх
blackbanny
Дата 22.7.2013, 16:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 83
Регистрация: 18.11.2009

Репутация: нет
Всего: нет



спасибо) посмотрел результат работы, вполне отлично)
Эталонная строка: BORDEAUX
Проверяемая строка: ")RDEAUXCHATEAUl'Estang ¦'ISDECASTILLOSotcastilio*con2008"
Результат проверки: ~~RDEAUX**************************************************
т.е. получается 6 из 8 или 75%

а не могли бы привести код метода для проверки?
PM MAIL   Вверх
Albor
Дата 22.7.2013, 16:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 589
Регистрация: 28.2.2009

Репутация: нет
Всего: 9



Вечерком выложу
PM MAIL ICQ   Вверх
Albor
Дата 22.7.2013, 21:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 589
Регистрация: 28.2.2009

Репутация: нет
Всего: 9



Сначала таблица для обеспечения работы алгоритма:
Код

// darray.h
//Класс двумерного массива для работы с функцией Левенштейна
//определяющей количество ошибок в тексте и место их расположения
//класс представляет собой таблицу, хранящую результат работы алгоритма Левенштейна
//и адреса ячеек для обратного прохода, определяющего место и тип ошибки
#if !defined(_DARRAY_CLASS_)
#define _DARRAY_CLASS_

struct Cell
{
    int value;
    Cell * pParentCell;
};
class CDArray
{
    Cell **table;
public:
    void Create(const int iLines, const int iColumns);
    CDArray();
    CDArray(const CDArray & cdarr);
    CDArray(const int iLineSize,const int iColumnSize);
    CDArray & operator=(const CDArray & cdarr);
    void GetSize(int * pLinesSize, int * pColumnsSize) const;
    Cell * GetCellAdress(const int iLineIndex, const int iColumnIndex) const;
    
    ~CDArray();
    Cell GetAt(const int iLineIndex,const int iColumnIndex) const;
    void SetAt(const int iLineIndex,const int iColumnIndex, const Cell cell);
private:
    int m_iColumns;
    int m_iLines;
};

#endif

Реализация:
Код

//darray.cpp
#include "stdafx.h"
#include "darray.h"

CDArray::CDArray()
{
    m_iLines=0;
    m_iColumns=0;
    table=0;
}

CDArray::CDArray(const int iLines,const int iColumns)
{
    m_iLines=iLines;
    m_iColumns=iColumns;
    table=new Cell*[m_iLines];
    for(int i=0;i<m_iLines; i++) table[i]=new Cell[m_iColumns];
    //////////////////////////////////////////////////////////////////////////
    // ------------- Инициализируем таблицу -------------
    for(i=0;i<m_iLines;i++) 
    {
        table[i][0].value =i;
        table[i][0].pParentCell= i==0?0:GetCellAdress(i-1,0);//&(table[i-1][0])
    }
    for(i=0;i<m_iColumns;i++) 
    {
        table[0][i].value=i;
        table[0][i].pParentCell= i==0?0:GetCellAdress(0,i-1);//&(table[0][i-1])
    }
}

CDArray::CDArray(const CDArray & cdarr)
{
    cdarr.GetSize(&m_iLines,&m_iColumns);
    table=new Cell*[m_iLines];
    for(int i=0;i<m_iLines; i++) table[i]=new Cell[m_iColumns];
    for(i=0;i<m_iLines;i++)
        for(int j=0;j<m_iColumns;j++)
            table[i][j]=cdarr.GetAt(i,j);
}

CDArray & CDArray::operator=(const CDArray &cdarr)
{//работает неправильно. При копировании адресов необходимо корректное копирование смещений.!!!!
    for(int k=0;k<m_iLines;k++) delete[]table[k];
    delete[]table;
    cdarr.GetSize(&m_iLines,&m_iColumns);
    table=new Cell*[m_iLines];
    for(int i=0;i<m_iLines; i++) table[i]=new Cell[m_iColumns];
    for(i=0;i<m_iLines;i++)
        for(int j=0;j<m_iColumns;j++)
            table[i][j]=cdarr.GetAt(i,j);
    return *this;
}

CDArray::~CDArray()
{
    for(int i=0;i<m_iLines;i++) delete[]table[i];
    delete[]table;
}

Cell CDArray::GetAt(const int iLineIndex,const int iColumnIndex) const
{
    return table[iLineIndex][iColumnIndex];
}

void CDArray::SetAt(const int iLineIndex,const int iColumnIndex, const Cell cell)
{
    table[iLineIndex][iColumnIndex]=cell;
}

Cell * CDArray::GetCellAdress(const int iLineIndex, const int iColumnIndex) const
{
    return &table[iLineIndex][iColumnIndex];
}

void CDArray::GetSize(int *pLinesSize, int *pColumnsSize) const
{// возвращает размеры массива в переданные адреса
    (*pLinesSize)=m_iLines;
    (*pColumnsSize)=m_iColumns;
}

void CDArray::Create(const int iLines, const int iColumns)
{
    m_iLines=iLines;
    m_iColumns=iColumns;
    table=new Cell*[m_iLines];
    for(int i=0;i<m_iLines; i++) table[i]=new Cell[m_iColumns];
    //////////////////////////////////////////////////////////////////////////
    // ------------- Инициализируем таблицу -------------
    for(i=0;i<m_iLines;i++) 
    {
        table[i][0].value =i;
        table[i][0].pParentCell= i==0?0:GetCellAdress(i-1,0);
    }
    for(i=0;i<m_iColumns;i++) 
    {
        table[0][i].value=i;
        table[0][i].pParentCell= i==0?0:GetCellAdress(0,i-1);
    }
}


Собственно сам алгоритм:
Код

void CTesstDlg::Levenshtein(const CString src, const CString dst, CDArray & table)
{// функция сравнивает строки и возвращает результирующую таблицу
    int i,j;// для работы с массивом
    int src_size=src.GetLength()+1;
    int dst_size=dst.GetLength()+1;
    table.Create(src_size,dst_size);
//////////////////////////////////////////////////////////////////////////
//--------------- поиск ошибок ---------------------

    char diff;
    int iErr(0);
    Cell cell;
    CString sResult;
    CString sTemp;
    for(i=1;i<src_size;i++)
    {
        for(j=1;j<dst_size;j++)
        {
            diff=src.GetAt(i-1)==dst.GetAt(j-1)?0:1;
            cell.value =__min(__min(table.GetAt(i-1,j).value+1,table.GetAt(i,j-1).value+1),table.GetAt(i-1,j-1).value+diff);
            iErr=cell.value;
            if(iErr==table.GetAt(i-1,j).value +1)
                cell.pParentCell = table.GetCellAdress(i-1,j);
            else if(iErr==table.GetAt(i,j-1).value+1)
                cell.pParentCell = table.GetCellAdress(i,j-1);
            else
                cell.pParentCell = table.GetCellAdress(i-1,j-1);
            table.SetAt(i,j,cell);
        }
    }
}


И его использование:
Код

//.......
const TCHAR INCORRECTSYMBOL('~');
const TCHAR ABSENTSYMBOL('@');
const TCHAR NOFOUNDSYMBOL('*');
//.......
void CTesstDlg::OnButton2() 
{// Нажатие кнопки "Проверить"
    UpdateData();
    CString sEtalon(m_sEtalon);    
    CString sTarget(m_sTest);
    CDArray table;
    Levenshtein(sEtalon,sTarget,table);

    int i;
    int j;
    table.GetSize(&i,&j);
    --i;--j;
    Cell * pCell=table.GetAt(i,j).pParentCell;
    m_sResult=sTarget;
    while(pCell!=0)
    {
        if(pCell == table.GetCellAdress(i-1,j))
        {//нужна вставка символа
            if(table.GetAt(i,j).value>pCell->value)    m_sResult.Insert(j,ABSENTSYMBOL);
            i--;
        }
        else if(pCell == table.GetCellAdress(i,j-1))
        {//лишний символ
            if(table.GetAt(i,j).value>pCell->value)    m_sResult.SetAt(j-1,NOFOUNDSYMBOL);
            j--;
        }
        else
        {//неверный символ
            if(table.GetAt(i,j).value>pCell->value)    m_sResult.SetAt(j-1,INCORRECTSYMBOL);
            i--;j--;
        }
        
        pCell=table.GetAt(i,j).pParentCell;
    }
    UpdateData(FALSE);
}

PM MAIL ICQ   Вверх
blackbanny
Дата 24.7.2013, 12:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 83
Регистрация: 18.11.2009

Репутация: нет
Всего: нет



большое спасибо за код)
есть небольшой вопрос...
Суть в следующем:
Эталонная строка: bordeaux

Проверяемая строка: <?)rdeaux??b1??i?hi??chateau?d£l'estang?11sdecastillo*?\t1'isdecastluo*c0,‘?2008?‘zszvssx****'?%?•0oironocrh*\ta??4^••ooiponot-?\t\t?•o-oi**\"1?vo,oc

Результат:***********b****************************************o~*******de*a***u*******************x************************************************************

Если проверяемую строку укоротить, например, до такой <?)rdeaux??b1??i?hi??chateau?d£l'estang?11sdecastillo, то результат будет таким ~~*rdeaux********************************************, что вполне корректно и ожидаемо smile

С чем может быть связана данная проблема? Есть ли какой-нибудь путь для ее обхода?
PM MAIL   Вверх
Albor
Дата 24.7.2013, 16:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 589
Регистрация: 28.2.2009

Репутация: нет
Всего: 9



Вполне вероятно, что у меня в программке есть незамеченные проблемы, это всё делалось на скорую руку и не проходило должного тестирования. Для меня было важнее на тот момент определиться, возможно ли решить задачу проверки текста на ошибки, но, в дальнейшем, данный функционал не потребовался и так и остался в виде теста. Попробую посмотреть в отладчике что к чему, но быстро не обещаю, так как свободного времени не очень много.
PM MAIL ICQ   Вверх
blackbanny
Дата 24.7.2013, 18:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 83
Регистрация: 18.11.2009

Репутация: нет
Всего: нет



буду очень благодарен)
PM MAIL   Вверх
Albor
Дата 26.7.2013, 12:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 589
Регистрация: 28.2.2009

Репутация: нет
Всего: 9



blackbanny, посмотрите эту статью, возможно в ней вы найдёте путь к решению (а может и решение) вашей задачи.
PM MAIL ICQ   Вверх
Albor
Дата 29.7.2013, 08:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 589
Регистрация: 28.2.2009

Репутация: нет
Всего: 9



Цитата

Эталонная строка: bordeaux

Проверяемая строка: <?)rdeaux??b1??i?hi??chateau?d£l'estang?11sdecastillo*?\t1'isdecastluo*c0,‘?2008?‘zszvssx****'?%?•0oironocrh*\ta??4^••ooiponot-?\t\t?•o-oi**\"1?vo,oc

Результат:***********b****************************************o~*******de*a***u*******************x************************************************************


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

Это сообщение отредактировал(а) Albor - 29.7.2013, 08:08
PM MAIL ICQ   Вверх
Albor
Дата 29.7.2013, 21:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 589
Регистрация: 28.2.2009

Репутация: нет
Всего: 9



Видимо всё значительно проще. Вот составил таблицу несколько упрощённого вашего теста
user posted image
Здесь видно, что для решения задачи нужно найти минимальное значение (либо несколько значений удовлетворяющих допустимому количеству ошибок) в последней колонке матрицы и, если нужно, то вычислить ошибки, либо обозначить диапазон подстрок(и), удовлетворяющих поиску.  
Добавлено:
Поторопился я с выводом, не всё так просто, чтобы в этом убедиться, нужно в вертикальную строку добавить текст строки для поиска, т.е. создать периодичность текста, тогда становится очевидным, что минимальным значением в последней колонке не отделаешься. 

Это сообщение отредактировал(а) Albor - 30.7.2013, 07:55
PM MAIL ICQ   Вверх
Страницы: (2) [Все] 1 2 
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.1161 ]   [ Использовано запросов: 20 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.