А как разобрать морфологически слово на части ?
От: TRAC Россия  
Дата: 16.12.05 13:55
Оценка:
Собственно, а как разобрать морфологически слово на части ?
Есть какой нибудь доступный алгоритм для выделения неменяющейся части слов?
ICQ ID: 5001408 (work)
ICQ ID: 5337528 (home)
Re: А как разобрать морфологически слово на части ?
От: Кодт Россия  
Дата: 17.12.05 09:03
Оценка:
Здравствуйте, TRAC, Вы писали:

TRA>Собственно, а как разобрать морфологически слово на части ?

TRA>Есть какой нибудь доступный алгоритм для выделения неменяющейся части слов?

На мой взгляд, это очень трудоёмкая задача.
Во-первых, омонимы. Во-вторых, йотированные гласные. В-третьих, меняющиеся корни.

Вот пример "три в одном"
Ноя — родительный падеж имени (Ной), (ной)[а]
Ноя — деепричастие глагола (ны)[ть], (н)[оя]

Так что на одном алгоритме, без БД по языку и без контекста — не уедешь.
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re: А как разобрать морфологически слово на части ?
От: mefrill Россия  
Дата: 17.12.05 20:00
Оценка:
Здравствуйте, TRAC, Вы писали:

TRA>Собственно, а как разобрать морфологически слово на части ?

TRA>Есть какой нибудь доступный алгоритм для выделения неменяющейся части слов?

Смотри transducer и morphology. Трансдьюсеры — это конечные автоматы, которые также для каждого состояния генерируют нечто. Например, для слова "колбасы" при чтении "колбас" генерит "колбаса", а при чтении "ы" генерит "родительный падеж", т.е. получаем "сущ." (значение "колбаса") + "Р.п.". Тебе надо будет выделить классы слов со стандратными изменениями и классы слов-исключений. Исключения придется кодировать каждое по отдельности. Корни надо самому будет забивать.
Re[2]: А как разобрать морфологически слово на части ?
От: mefrill Россия  
Дата: 17.12.05 20:08
Оценка:
Здравствуйте, mefrill, Вы писали:

Вот еще глава про трансдьюсеры из Джуравски и Мартина — Speech and Language Processing.
Re[3]: А как разобрать морфологически слово на части ?
От: TRAC Россия  
Дата: 20.12.05 14:18
Оценка:
Меня интересует получение из слов неменяющихся частей
В инете упоминается алгоритм стеминга или стиминга незнаю как правильно
Что он собственно собой представляет, есть ли какой доступный алгортим ?
ICQ ID: 5001408 (work)
ICQ ID: 5337528 (home)
Re[4]: А как разобрать морфологически слово на части ?
От: mefrill Россия  
Дата: 21.12.05 06:52
Оценка:
Здравствуйте, TRAC, Вы писали:

TRA>Меня интересует получение из слов неменяющихся частей

TRA>В инете упоминается алгоритм стеминга или стиминга незнаю как правильно
TRA>Что он собственно собой представляет, есть ли какой доступный алгортим ?

Тебе надо понять, что выделение из слова (из плоской последовательности символом) какой-либо структуры называется синтаксическим анализом. Т.е. у тебя по факту стоит задача провести синтаксический анализ слов естественного языка. Вопрос в алгоритме. Алгоритм должен быть подходящим для языка, а язык слов — это регулярный (в терминологии Хомского) язык. Для синтаксического анализа регулярных языков используется формализм под названием "конечный автомат". Конечный автомат состоит из множества состояний, каждое из которых означает, что определенная часть текста прочитана. Есть конечное состояние, означающее, что все что тебе нужно прочитано. Вот тебе надо создать такой конечный автомат. Как это сделать написано в главе из Джуравски и Мартина, ссылку на которую я тебе дал. Можно использовать иные подходы, но в любом случае без явного кодиирования множества корней слов русского языка, а также множества правил изменений этих слов тебе не обойтись. Дело здесь не в магическом алгоритме, которого на самом деле не существует, т.к. сама алгоритмическая задача относительно проста, а в огромном массиве данных, которые ты вынужден будешь вручную ввести (или не вручную, взять какую-нибудь базу из Сети). Лучшим решением (самым быстрым и экономичны) является конечный автомат, который на выходе выдает этот смый корень слова. Но можешь еще что-нибудь использовать, это непринципиально.
Re: А как разобрать морфологически слово на части ?
От: Lepsik Индия figvam.ca
Дата: 10.01.06 20:07
Оценка:
TRA>Собственно, а как разобрать морфологически слово на части ?
TRA>Есть какой нибудь доступный алгоритм для выделения неменяющейся части слов?

для какого языка ?

для английского почти просто



//---------------------------------------------------------------------------
/*
porter.cpp

Description:
    strip english word

AUTHOR    : Stuart J. Barr 
 * DATE:    : c. September 1986, give or take a few months...
Modification:
   Lepsik
*/
//---------------------------------------------------------------------------

#include <string.h>
#include <string>
#include <stdio.h>
#include "str_ext.h"

#pragma warning(disable: 4996) // was declared deprecated
#pragma warning(disable:4267)

#pragma setlocale(".1252")

#define KEYWORDSIZE 64

#define BIG_KEYWORDSIZE (KEYWORDSIZE + KEYWORDSIZE+20)

using namespace std;
using namespace sts;
//-------------------------------------------------------------------------------------------------------------------------------
static void to_lower_case ( char *kwd )
{
    try
    {
        size_t len = strlen(kwd);
        for( size_t i = 0 ; i < len ; i++ )
        {
            if( (kwd[i] >= 'A') && (kwd[i] <= 'Z') )
            {
                kwd[i] += 'a' - 'A';
            }
        }
    }catch(...){}
}
//-------------------------------------------------------------------------------------------------------------------------------
static bool isvalid( const char l )
{
    try
    {
        if( (l >= 'a') && (l <= 'z') )
        {
            return false;
        }else if( (l >= 'A') && (l <= 'Z') )
        {
            return false;
        }else if( (l >= '0') && (l <= '9') )
        {
            return false;
        }
    }catch(...){}
    return true;
}
//-------------------------------------------------------------------------------------------------------------------------------
static void clean( char *kwd )
{
    if( kwd == NULL )
    {
        return;
    }
    try
    {
        size_t last = strlen(kwd);
        for( size_t i = 0 ; i < last ; i++ ) 
        {
            if( isvalid( kwd[i]) != 0 ) 
            {
                for(size_t j = i ; j < last-1 ; j++ )
                {
                    kwd[j] = kwd[j+1];
                }
                kwd[last-1] = '\0';
                last--;
                i--;
            }
        }
    }catch(...){}
}
//-------------------------------------------------------------------------------------------------------------------------------
static bool has_suffix ( const char *word, const char *suffix, char *stem )
{
    char tmp[BIG_KEYWORDSIZE] = {0};
    try
    {
        size_t sz_word = strlen(word);
        size_t sz_suffix = strlen(suffix);
        if( sz_word <= sz_suffix )
        {
            return false;
        }
        size_t widx = sz_word - 2;
        size_t sidx = sz_suffix - 2;
        char wc = word[widx];
        char sc = suffix[sidx];
        if( (sz_suffix > 1) && ( wc != sc ) )
        {
            return false;
        }
        strset ( stem, '\0' );
        size_t nct = sz_word - sz_suffix;
        strncat ( stem, word, nct );
        strncpy ( tmp, stem, sizeof(tmp)-1 );
        strcat ( tmp, suffix );

        return ( strcmp (  tmp, word ) == 0 );
    }catch(...){}
    return false;
}
//-------------------------------------------------------------------------------------------------------------------------------
static bool vowel ( const char ch, const char prev )
{
    switch( ch ) 
    {
        case 'a':
        case 'e':
        case 'i':
        case 'o':
        case 'u': return true; 
            break;
        case 'y': return vowel( prev,'?' ); 
            break;
        default : return false;
            break;
    }
    return false;
}
//-------------------------------------------------------------------------------------------------------------------------------
static bool contains_vowel( const char *word )
{
    if( NULL == word )
    {
        return false;
    }
    try
    {
        size_t length = strlen(word);
        for( size_t i=0 ; i < length; i++ )
        {
            if ( i > 0 ) 
            {
                if( vowel( word[i], word[i-1]) )
                {
                    return true;
                }
            }
            else 
            {    
                if( vowel( word[0], 'a' ) )
                {
                    return true;
                }
            }
        }
    }catch(...){}
    return false;
}
//-------------------------------------------------------------------------------------------------------------------------------
static bool cvc( const char *str )
{
    if( str == NULL )
    {
        return false;
    }
    try
    {
        size_t length = strlen(str);
        if( length < 3 )
        {
            return false;
        }
        if( !vowel ( str[ length-1], str[length-2] )
                && ( str[ length-1] != 'w' )
                && ( str[ length-1] != 'x' )
                && ( str[ length-1] != 'y' )
                && vowel ( str[length-2], str[length-3] )
                && ( ( ( length == 3 ) && !vowel( str[0], 'a' ) )
                || !vowel(  str[length-3], str[length-4]) ) )
        {
            return true;
        }
    }catch(...){}
    return false;
}
//-------------------------------------------------------------------------------------------------------------------------------
static size_t measure( const char *stem )
{
    if( stem == NULL )
    {
        return 0;
    }
    try
    {
        size_t length = strlen(stem);
        size_t count = 0;
        for( size_t i = 0; i < length; ) 
        {
            for( ; i < length ; i++ ) 
            {
                if( i > 0 ) 
                {
                    if( vowel( stem[i], stem[i-1] ) )
                    {
                        break;
                    }
                }
                else if( vowel( stem[i], 'a' ) )
                {
                        break;
                }
            }
            for( i++ ; i < length ; i++ ) 
            {
                if ( i > 0 ) 
                {
                    if( !vowel( stem[i], stem[i-1] ) )
                    {
                        break;
                    }
                }
                else if( !vowel( stem[i], '?' ) )
                {
                        break;
                }
            }
            if( i < length ) 
            {
                count++;
                i++;
            }
        }
        return count;
    }catch(...){}
    return 0;
}
//-------------------------------------------------------------------------------------------------------------------------------
static void strip_prefixes( char *str )
{
    if( str == NULL )
    {
        return;
    }
    static const char *prefixes[] = { "kilo", "micro", "milli", "intra", "ultra", "mega", "nano", "pico", "pseudo", "super", 0 };
    try
    {
        for( size_t i=0 ; prefixes[i] != 0 ; i++ ) 
        {
            if( strncmp( prefixes[i], str, strlen(prefixes[i]) ) == 0 ) 
            {
                size_t j = 0;
                for( ; j < strlen(str) - strlen( prefixes[i] ) ; j++ )
                {
                    str[j] = str[j + strlen( prefixes[i]) ];
                }
                str[j] = '\0';
                return;
            }
        }
    }catch(...){}
}
//-------------------------------------------------------------------------------------------------------------------------------
static void step_1( char *str )
{
    if( str == NULL )
    {
        return;
    }
    char stem[BIG_KEYWORDSIZE] = {0};
    try
    {
        if( str[strlen(str)-1] == 's' ) 
        {
            if( has_suffix(str, "sses", stem ) || has_suffix(str, "ies", stem ) )
            {
                str[strlen(str)-2] = '\0';
            }else if( str[strlen(str)-2] != 's' )
            {
                    str[strlen(str)-1] = '\0';
            }
        }
        if( has_suffix(str, "eed", stem) ) 
        {
            if( measure(stem) > 0 )
            {
                str[strlen(str)-1] = '\0';
            }
        }else 
        {    
            if( ( has_suffix(str, "ed", stem ) || has_suffix(str,"ing",stem) ) 
                && contains_vowel(stem) ) 
            {
                str[strlen(stem)] = '\0';
                if( has_suffix(str,"at",stem ) || has_suffix(str,"bl",stem ) || has_suffix(str,"iz",stem ) ) 
                {
                    str[strlen(str)+1] = '\0';
                    str[strlen(str)] = 'e';
                }
                else
                {    
                    int length = strlen(str);
                    if( (str[length-1] == str[length-2])
                            && (str[length-1] != 'l')
                            && (str[length-1] != 's')
                            && (str[length-1] != 'z') )
                    {
                        str[length-1] = '\0';
                    }else if( measure(str) == 1 ) 
                    {
                            if( cvc(str) ) 
                            {
                                str[strlen(str)+1] = '\0';
                                str[strlen(str)] = 'e';
                            }
                    }
                }
            }
        }
        if( has_suffix( str, "y", stem ) && contains_vowel( stem ) )
        {
            str[strlen(str)-1] = 'i';
        }
    }catch(...){}
}
//-------------------------------------------------------------------------------------------------------------------------------
static void step_2( char *str )
{
    if( NULL == str )
    {
        return;
    }
    static char *suffixes[][2] =  { 
                    { "ational", "ate" },
                    { "tional",  "tion" },
                    { "enci",    "ence" },
                    { "anci",    "ance" },
                    { "izer",    "ize" },
                    { "iser",    "ize" },
                    { "abli",    "able" },
                    { "alli",    "al" },
                    { "entli",   "ent" },
                    { "eli",     "e" },
                    { "ousli",   "ous" },
                    { "ization", "ize" },
                    { "isation", "ize" },
                    { "ation",   "ate" },
                    { "ator",    "ate" },
                    { "alism",   "al" },
                    { "iveness", "ive" },
                    { "fulness", "ful" },
                    { "ousness", "ous" },
                    { "aliti",   "al" },
                    { "iviti",   "ive" },
                    { "biliti",  "ble" },
                    {  0,        0     } };
    char stem[BIG_KEYWORDSIZE] = {0};
    try
    {
        for( size_t index = 0 ; suffixes[index][0] != 0 ; index++ ) 
        {
            if( has_suffix( str, suffixes[index][0], stem ) ) 
            {
                if( measure( stem ) > 0 ) 
                {
                    sprintf( str, "%s%s", stem, suffixes[index][1] );
                    return;
                }
            }
        }
    }catch(...){}
}
//-------------------------------------------------------------------------------------------------------------------------------
static void step_3( char *str )
{
    if( NULL == str )
    {
        return;
    }
    static char *suffixes[][2] =  { 
                    { "icate", "ic" },
                    { "ative", "" },
                    { "alize", "al" },
                    { "alise", "al" },
                    { "iciti", "ic" },
                    { "ical",  "ic" },
                    { "ful",   "" },
                    { "ness",  "" },
                    {  0,        0     } };
    char stem[BIG_KEYWORDSIZE] = {0};
    try
    {
        for( size_t index = 0 ; suffixes[index][0] != 0 ; index++ ) 
        {
            if( has_suffix( str, suffixes[index][0], stem ) ) 
            {
                if( measure( stem ) > 0 ) 
                {
                    sprintf( str, "%s%s", stem, suffixes[index][1] );
                    return;
                }
            }
        }
    }catch(...){}
}
//-------------------------------------------------------------------------------------------------------------------------------
static void step_4( char *str )
{
    if( str == NULL )
    {
        return;
    }
    static char *suffixes[] = { "al", "ance", "ence", "er", "ic", "able", "ible", "ant", "ement", "ment", 
                                "ent", "sion", "tion", "ou", "ism", "ate", "iti", "ous", "ive", "ize", "ise", 0 };
    char stem[BIG_KEYWORDSIZE] = {0};
    try
    {
        for( size_t index = 0 ; suffixes[index] != 0 ; index++ ) 
        {
            if( has_suffix ( str, suffixes[index], stem ) )
            {
                if ( measure ( stem ) > 1 ) 
                {
                    strcpy( str, stem );
                    return;
                }
            }
        }
    }catch(...){}
}
//-------------------------------------------------------------------------------------------------------------------------------
static void step_5( char *str )
{
    if( str == NULL )
    {
        return;
    }
    try
    {
        if( str[strlen(str)-1] == 'e' ) 
        {
            // measure(string)==measure(stem) if ends in vowel 
            if( measure(str) > 1 )
            {
                str[ strlen(str)-1 ] = '\0';
            }
            else
            {
                if( measure(str) == 1 ) 
                {
                    char stem[BIG_KEYWORDSIZE];
                    strcpy(stem,"");
                    strncat( stem, str, strlen(str)-1 );
                    if( !cvc(stem) )
                    {
                        str[ strlen(str)-1 ] = '\0';
                    }
                }
            }
        }
        if( (str[strlen(str)-1] == 'l' ) && (str[strlen(str)-2] == 'l') && (measure(str) > 1) )
        {
            str[strlen(str)-1] = '\0';
        }
    }catch(...){}
}
//-------------------------------------------------------------------------------------------------------------------------------
static void strip_suffixes( char *str )
{
    if( str == NULL )
    {
        return;
    }
    try
    {
        step_1 ( str );
        step_2 ( str );
        step_3 ( str );
        step_4 ( str );
        step_5 ( str );
    }catch(...){}
}
//-------------------------------------------------------------------------------------------------------------------------------
static void strip_affixes( char *str, bool prefix )
{
    if( str == NULL )
    {
        return;
    }
    try
    {
        to_lower_case( str );
        clean( str );
        if( prefix )
        {
            strip_prefixes( str );
        }
        strip_suffixes( str );
        str[KEYWORDSIZE] = '\0';
    }catch(...){}
}
//-------------------------------------------------------------------------------------------------------------------------------
void strip1252( const wstring &strIn, wstring &strOut )
{
    try
    {
        const size_t ln = strIn.length();
        if( ln <= 0 )
        {
            return;
        }
        string nstr;
        w2s( nstr, strIn, 1252 );
        char szword[255] = {0};
        strncpy( szword, nstr.c_str(), sizeof(szword)-1 );

        strip_affixes( szword, true );
        nstr = szword;
        s2w( strOut, nstr, 1252 );
    }catch(...){}
}
//-------------------------------------------------------------------------------------------------------------------------------
Re: А как разобрать морфологически слово на части ?
От: buriy Россия http://www.buriy.com/
Дата: 10.01.06 22:56
Оценка:
Здравствуйте, TRAC, Вы писали:

TRA>Собственно, а как разобрать морфологически слово на части ?

TRA>Есть какой нибудь доступный алгоритм для выделения неменяющейся части слов?

Задача сложная, хотя есть простые приближенные решения.
Смотри AOT.RU, там есть достаточно качественное решение в виде бесплатного и очень быстрого COM-модуля.
/bur
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.