最大匹配演算法

『壹』 為什麼中文分詞的幾大主流分詞技術，沒有用逆向最大匹配或者雙向最大匹配分詞演算法的呢

速度是關鍵，逆向最大匹配需要專門創建逆向匹配索引。操作維護比較麻煩

『貳』 二分圖最大匹配Matlab程序（在線等，感激不盡！）

第一個問題比較簡單，這里懶得對著你的圖片敲數據，用隨機數代替

long=100;

A=0.1*rand(long,1);

B=0.15*rand(long,1);

[AA BB]=meshgrid(A,B);

gg=0.5017*AA-0.65*BB;

g=gg>=-0.03&gg<=0.03; %這就是gij矩陣，相當於二分圖的連接矩陣

[num h] = maxnum(g);%第二個問題就是求二分圖的最大匹配問題，這里

%調用了一個自己寫maxnum函數，返回num就是最大值，h是hij(不唯一）

以下是maxnum.m的內容，用的是匈牙利演算法

其中還用了一個遞歸的incpath函數，尋找增廣路徑

function[numh]=maxnum(g)
s=size(g);
globalG_h;%矩陣hij記錄選中
globalG_g;%矩陣gij記錄匹配
globalG_v;%記錄當前一次路徑訪問過的節點
G_h=false(s);%矩陣hij初始為空
G_g=g;%矩陣gij就是傳遞進來的參數g
fori=1:s(1)
G_v=false(1,s(2));%每次初始化徑訪問過的節點為空
incpath(i);%從Ai開始尋找增廣路徑
end
h=G_h;num=sum(h(:));%輸出最大匹配數，和匹配矩陣h
clearglobal'G_h';clearglobal'G_g';
end

functionOK=incpath(i)%從Ai開始
globalG_h;globalG_g;globalG_v;OK=false;
j=find(~G_h(i,:)&G_g(i,:)&~G_v,1);%尋找合條件的Bj
ifisempty(j),return;end%找不到返回false
G_v(j)=true;%找到了，標記Bj為以訪問節點
ii=find(G_h(:,j));%尋找Bj在原來匹配中
ifisempty(ii)%如果不在原匹配中
G_h(i,j)=true;OK=true;return;end%找到增廣路徑末端，返回true
ok=incpath(ii);%如果在原來的匹配中，根據匹配對應的Aii遞歸調用incpath尋找
ifok%如果遞歸尋找返回成功
G_h(i,j)=~G_h(i,j);G_h(ii,j)=~G_h(ii,j);OK=true;return;end%路徑反色返回true
end

『叄』 求一般圖的最大權匹配的演算法（最好詳細一些，注意數最大權匹配），高分求助！

Algorithmus 3.3 Kruskal's Algorithm 時間復雜度 O(mlog n)
m邊數 n點數
輸入: 圖 G = (V;E) 和 權c : E -》R.
輸出: 一棵最優樹 T.
begin
把所有邊以權的大小按從小到大排序
T := (VG，ET ) := (VG， 空);
for i = 1 to m do
if T + ei 沒有圈 then
T := (VG;ET 並上 {ei});
if end
for end
end

或者 Algorithmus 3.5 Prim's Algorithm 時間復雜度O(m+n log n)

『肆』 用匈牙利演算法求最大匹配唯一么

不惟一。擴張的順序不同，枚舉頂點的順序不同，解就不一定相同

『伍』 圖的最大匹配演算法的c或c++實現

匈牙利演算法
#include<iostream>
#include<string>
#include<vector>
using namespace std;
bool mark1[100],mark2[100];
int list[100];
int n,m,edge,num;c
ector<vector<int> > v;
bool dfs(int to)
{
register int i,point,s = list[to];
for(i=0;i<v[s].size();i++)
{
point = v[s][i];
if(!mark2[point])
continue;
mark2[point] = false;
if(list[point]==-1 || dfs(point)){
list[point] = s;
return true;
}
}
return false;
}
void Solve()
{
int i,j,point;
bool flog = false;
memset(mark1,true,sizeof(mark1));
memset(list,-1,sizeof(list));
num=0;
for(i=0;i<n;i++)
{
for(j=0;j<v[i].size();j++)
if(list[v[i][j]] == -1)
{
mark1[i] = false;
list[v[i][j]] = i;
num++;
if(i==0) flog = true;
break;
}
}
for(i=0;i<n;i++)
{
if(mark1[i])
{
if(!v[i].empty()){
memset(mark2,true,sizeof(mark2));
for(j=0;j<v[i].size();j++)
{
point = v[i][j];
if(!mark2[point]) continue;
mark2[point] = false;
if(list[point] == -1 || dfs(point))
{
list[point] = i;
num++;
break;
}
}
}mark1[i] = false;
}
}
if(flog || list[0] != -1)
cout << num-1 << endl;
else cout << num << endl;
}
int main()
{
int i,j,s,d;
while(cin>>n)
{
if(n == 0)break;
v.clear();
v.resize(n);
cin >> m >> edge;
for(i=0;i<edge;i++)
{
cin >> j >> s >> d;
v[s].push_back(d);
}
Solve();
}
return 0;
}

『陸』 最大匹配演算法中，如何組織和存儲詞典

主要看你的詞表結構了，最大詞長的初始值，查詞典的次數和匹配的次數，然後得出時間復雜度，原始hash演算法復雜度沒記錯的話應該是2.89，11年看過一個文獻，提出一種改進的演算法時間復雜度是2.291…… 另外

『柒』 中文分詞中正向最大匹配演算法的分詞速度是多少准確率大概為多少

主要看你的詞表結構了，最大詞長的初始值，查詞典的次數和匹配的次數，然後得出時間復雜度，原始hash演算法復雜度沒記錯的話應該是2.89，11年看過一個文獻，提出一種改進的演算法時間復雜度是2.291……

另外，分詞演算法並不是原封不動的，比如有些搜索引擎的詞表結構就採用tire樹結構，這樣不用設置最大詞長，不過內存空間方面就要有取捨，甚至還有採用減少查典次數增加匹配次數的搜索引擎……
所以單純的給你一個189.3m/M純內存分詞速度，但是這演算法換個台更高配置的伺服器卻變成了497.6ms/M，這沒有任何意義……
記得哪個文獻上有人說，分詞本身不是目的，而是後續處理過程的必要階段，所以，除非你是研究演算法的，否則單純追求這東西的速度和准確率沒什麼太大意義

『捌』 matlab用正向最大匹配演算法實現中文分詞！急！！！

sqlConnection con = new SqlConnection
con.Open();
string sqlstr = "sql語句";
SqlDataAdapter da = new SqlDataAdapter(sqlstr, con);
DataSet ds= new DataSet();
da.Fill(ds);
dataGridView1.DataSource = ds.Tables[0];
con.Close();

『玖』 什麼叫正向最大匹配演算法,反向最大匹配演算法

分詞演算法里的吧

比如 我是一個好人

由於 詞語很多，所以分詞中先設定一個可能的，最長的片語的詞數
比如說，我認定最長的片語是3個字，那在比對中，會將句子3個字為始進行比對
正向匹配演算法好象是從左到右 反向區域演算法是從右到左，具體忘記了

以 「我是一個好人」 為例

正向的順序為
我是一
我是
我 ===> 得到一個詞
是一個
是一
是 ===>得到一個詞
一個好
一個===> 得到一個詞
好人===>得到一個詞
結果 我、是、一個、好人

反向演算法
個好人
好人==> 好人
是一個
一個==> 一個
我是
是==> 是
我==> 我
結果 我、是、一個、好人

『拾』 求二分圖最大匹配的最大流演算法，附Pascal程序

program bgf;
const maxn=402;
var map:array[1..maxn,1..maxn]of longint;
hash:array[1..maxn]of boolean;
n,m,ans:longint;

procere init;
var i,j,x,s:longint;
begin
readln(n,m);
fillchar(map,sizeof(map),0);
for i:=2 to n+1 do map[1,i]:=1;
for i:=1 to n do
begin
read(s);
for j:=1 to s do
begin
read(x);
map[i+1,x+n+1]:=1;
end;{for}
readln;
end;{for}
for i:=n+2 to n+m+1 do map[i,n+m+2]:=1;
n:=n+m+2;
end;{init}

function min(a,b:longint):longint;
begin
if a<b then exit(a)
else exit(b);
end;{min}

function DFS(u,low:longint):longint;
var i,num:longint;
begin
if u=n then exit(low);
if hash[u] then exit(0);
hash[u]:=true;
for i:=1 to n do
if (map[u,i]>0)and(not hash[i]) then
begin
num:=DFS(i,min(low,map[u,i]));
if num>0 then
begin
dec(map[u,i],num);
inc(map[i,u],num);
exit(num);
end;{if}
end;{if}
exit(0);
end;{DFS}

procere calc;
var flow:longint;
begin
ans:=0;
repeat
fillchar(hash,sizeof(hash),0);
flow:=DFS(1,maxint);
if flow>0 then ans:=ans+flow;
until flow<=0;
end;{calc}

procere print;
begin
writeln(ans);
end;{print}

begin{main}
init;
calc;
print;
end.