Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > сравнение строк


Автор: blackbanny 17.7.2013, 12:41
Доброго времени суток!
Имеется список слов и некий получаемый текст. Нужно перебирать список слов и искать эти слова в получаемом тексте. Проблема в том, что получаемый текст может приходить с ошибками, например, в словаре есть такое слово "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 "
пробелы в получаемом тексте скорее всего нужно будет убрать(это делается просто стандартными функциями языка), а вот как действовать дальше? 

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


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

вообщем должна быть какая то вероятностная модель по идее. 

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

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

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

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

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

Думаю с такими ошибками лучше всего справится Левенштейн. Можно попробовать собрать статистику ошибок и улучшить алгоритм, но сомневаюсь что это даст прирост более 1/1000.
Тут надо улучшать обработку перед OCR.
А так совет один трудитесь. Чем больше придумаете тем лучше будет.

Автор: mrgloom 18.7.2013, 08:09
Цитата

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


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

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

с помощью какого алгоритма можно узнать насколько совпадает?

Автор: mrgloom 18.7.2013, 16:51
по-моему это называется Approximate string matching
http://en.wikipedia.org/wiki/Approximate_string_matching

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

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

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

Автор: blackbanny 19.7.2013, 06:40
конечно интересно, было бы интересно посмотреть smile

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

Присоединил к предыдущему сообщению, иначе почему-то не отправлялось.

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

а не могли бы привести код метода для проверки?

Автор: Albor 22.7.2013, 16:35
Вечерком выложу

Автор: Albor 22.7.2013, 21:10
Сначала таблица для обеспечения работы алгоритма:
Код

// 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);
}

Автор: blackbanny 24.7.2013, 12:07
большое спасибо за код)
есть небольшой вопрос...
Суть в следующем:
Эталонная строка: 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

С чем может быть связана данная проблема? Есть ли какой-нибудь путь для ее обхода?

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

Автор: blackbanny 24.7.2013, 18:12
буду очень благодарен)

Автор: Albor 26.7.2013, 12:40
blackbanny, посмотрите http://algolist.manual.ru/search/lcs/, возможно в ней вы найдёте путь к решению (а может и решение) вашей задачи.

Автор: Albor 29.7.2013, 08:07
Цитата

Эталонная строка: 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, 21:08
Видимо всё значительно проще. Вот составил таблицу несколько упрощённого вашего теста
user posted image
Здесь видно, что для решения задачи нужно найти минимальное значение (либо несколько значений удовлетворяющих допустимому количеству ошибок) в последней колонке матрицы и, если нужно, то вычислить ошибки, либо обозначить диапазон подстрок(и), удовлетворяющих поиску.  
Добавлено:
Поторопился я с выводом, не всё так просто, чтобы в этом убедиться, нужно в вертикальную строку добавить текст строки для поиска, т.е. создать периодичность текста, тогда становится очевидным, что минимальным значением в последней колонке не отделаешься. 

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)