VPF::сравнение строк - Форум программистов

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 "
пробелы в получаемом тексте скорее всего нужно будет убрать(это делается просто стандартными функциями языка), а вот как действовать дальше?

mrgloom

Дата 17.7.2013, 15:07 (ссылка)

(нет голосов)

Загрузка ...

Опытный

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

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

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

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

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

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-ой позиции

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

Pavia

Дата 17.7.2013, 17:22 (ссылка)

(нет голосов)

Загрузка ...

Опытный

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

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

Цитата(blackbanny @ 17.7.2013, 12:41

)

Подойдет ли алгоритм расстояние Левенштейна или есть более эффективные алгоритмы?

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

mrgloom

Дата 18.7.2013, 08:09 (ссылка)

(нет голосов)

Загрузка ...

Опытный

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

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

Цитата

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

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

blackbanny

Дата 18.7.2013, 16:37 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

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

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

Цитата(mrgloom @ 18.7.2013, 08:09

)

смотреть насколько совпадает.

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

mrgloom

Дата 18.7.2013, 16:51 (ссылка)

(нет голосов)

Загрузка ...

Опытный

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

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

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

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

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

blackbanny

Дата 19.7.2013, 06:40 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

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

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

конечно интересно, было бы интересно посмотреть smile

Albor

Дата 19.7.2013, 07:22 (ссылка)

(нет голосов)

Загрузка ...

Опытный

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

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

Цитата(blackbanny @ 19.7.2013, 05:40

)

конечно интересно, было бы интересно посмотреть

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

blackbanny

Дата 22.7.2013, 16:26 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

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

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

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

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

Albor

Дата 22.7.2013, 16:35 (ссылка)

(нет голосов)

Загрузка ...

Опытный

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

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

Вечерком выложу

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

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

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

Albor

Дата 24.7.2013, 16:02 (ссылка)

(нет голосов)

Загрузка ...

Опытный

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

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

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

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