問題タブ [greedy]

htmlフレームソースを使用して、多数の画像の自動ダウンロードを行っています。So fra、so good、Sed、wget。フレームソースの例：

だから私はこれを行います：

このような部分を取得するには：

次にこれを行うには：

wget --base = / some / url / concept_Core.jpg

しかし、厄介な線が1つあります。その行は、明らかに、サイトのバグ、またはそれが何であれ、それが間違っているので、変更することはできません。;）

つまり、これらの「concept_Frigate16.jpg」のうちの2つが1行に並んでいます。そして私のスクリプトは私に与えます

あなたはその理由を理解しています。Sedは貪欲で、この場合は明らかにこれが現れます。

さて、問題は、どうすればこのコーナーケースを取り除くことができるかということです。つまり、貪欲ではなく、最初の.jpgで停止しますか？強調されたテキスト

動的計画法または貪欲な方法のどちらを使用するかを決定できるように、問題にはどのようなプロパティが必要ですか?

IIS 7.5（Windows Web Server 2008 R2）で汎用URL書き換えルールを作成したいと思います。

次のURLと一致させたい：

www.mysite.com/param
www.mysite.com/folder1/
www.mysite.com/folder1/param
www.mysite.com/folder1/folder2/
www.mysite.com/folder1/folder2/param

フォルダーと一致させたい場合は、末尾のスラッシュ（/）に注意してください。それ以外の場合は、パラメーターです。

次の書き換えルールを設定しました。

{R：1}、{R：2}、{R：3}の3つの一致する句があります。ただし、次のtest-URLを入力すると：

folder1 / param

次の応答があります。

{R：1}は空です
{R：2} = folder1
{R：3} = param

私は次の応答を疑った：

{R：1} = folder1
{R：2}は空です
{R：3} = param

つまり、folder1をリライトパターンの最初の部分にマップする必要があります。

書き換えルールを次のようにマップしたいと思います。

マッチを貪欲にする、つまり最初の可能な句にマッチさせるために私は何が欠けていますか？

Java を使用してグラフの色付けプロジェクトに取り組んでいます。四色定理を使用して、4 つの異なるグラフ色付けアルゴリズムを実装する必要があります。少数の隣人貪欲アルゴリズムという名前のアルゴリズムの 1 つに問題があります。

多数のポリゴン オブジェクト (arraylist に格納されている) を含むマップがあります。また、さまざまなポリゴンの隣接関係を表す 2D ブール配列があります。

私はアルゴリズムを理論的に知っています。色付けされていないポリゴンを格納するプライオリティ キューがあります。隣接数に基づくキューの順序。隣接するポリゴンが少ない場合、隣接するポリゴンが多いポリゴンよりも優れていると見なされます。いずれにせよ、アルゴリズムは優先度キューからポリゴンを繰り返し描画し、隣接関係に基づいて色付けを試みる必要があります。

残念ながら、実装部分に問題があります。隣接数に基づいてプライオリティ キューを取得しましたが、それらのポリゴンに色を割り当てる際に問題が発生しました。その種のアルゴリズムに取り組んだ人、またはアイデアを持っている人がいる場合は、私と共有してください. 実装部分を高速化するためのアイデアが必要です。

前もって感謝します。

ANTLR 文法には次のようなルールがあります。

このルールは単純に C スタイルのコメントに一致するため、/* と */ の間にある任意のテキストを含む任意のペアを受け入れ、正常に機能します。

ここでやりたいことは、ルールが一致したときに /* と */ の間のすべてのテキストをキャプチャして、アクションにアクセスできるようにすることです。このようなもの：

このアプローチは機能しません。解析中に「/*」の後の最初の文字に到達すると、「実行可能な代替手段はありません」となります。

これを行うことができるかどうか、またはどのように行うことができるかについては、よくわかりません。提案やガイダンスを歓迎します。

私が欲しい

なる

これを達成するために、私は

しかし、この正規表現は

の中へ

それ以外の

誰かが変更する正規表現を構築するのを手伝ってくれますか

の中へ

Javaの正規表現を使用して、次のような文字列を照合およびキャプチャしています。

0::10000

解決策は次のとおりです。

(0::\d{1,8})

ただし、入力の一致は成功します

10::10000

同様に、それは間違っています。したがって、私は今持っています：

[^\d](0::\d{1,8})

つまり、数字以外の文字でリードする必要がありますが、最初のゼロの前に何らかの文字が必要であることを意味します。私が本当に望んでいること（そして私が助けを必要としていること）は、「数字がないか、まったくない状態でリードする」と言うことです。

結論として、最終的なソリューションの正規表現は次のように一致する必要があります。

0::10000
kjkj0::10000

次のものと一致しないようにする必要があります。

10::10000

このサイトは、誰かが助けたい場合に役立つかもしれません。

ありがとう。

私は正規表現にかなりの経験がありますが、論理和を含む現在のアプリケーションでは問題があります。

私の状況は次のとおりです。アドレスの「識別子要素」の正規表現の一致に基づいて、アドレスを構成要素に分離する必要があります。同等の英語の例は、「state」、「road」、「 boulevard」-たとえば、これらを住所に書き留めた場合。次のようなアドレスがあるとします。ここで（これは英語では発生しません）、各名前の後に識別子の種類を指定しました

United States COUNTRY California STATE San Francisco CITY Mission STREET 345 NUMBER

（CAPSの単語は私が「識別子」と呼んでいるものです）。

これを次のように解析します。
United States COUNTRY
California STATE
San Francisco CITY
Mission STREET
245 NUMBER


OK、これは確かに英語のために考案されたものですが、ここに問題があります。私は中国語のデータを扱っています。実際、このスタイルの識別子の指定は常に行われています。以下の例：

云南-省 ; 丽江-市 ; 古城-区 ; 西安-街 ; 杨春-巷 ; Yunnan-Province ; LiJiang-City ; GuCheng-District ; Xi'An-Street ; Yangchun-Alley

これは非常に簡単です。論理和リストに分けられた、潜在的な候補識別子名の怠惰な一致です。

中国の場合、以下は「州レベル」のエンティティです。

省 (Province) , 自治区 (Autonomous Region) , 市 (Municipality)

したがって、これまでの私の正規表現は次のようになります。

(.+?(?:(?:省)|(?:自治区)|(?:市)))

アドレスのさまざまな部分を説明するために、これらのシリーズがあります。たとえば、都市に対応する次のレベルは次のとおりです。

(.+?(?:(?:地区)|(?:自治州)|(?:市)|(?:盟)))

したがって、州のエンティティとそれに続く都市のエンティティを一致させるには、次のようにします。

(.+?(?:(?:省)|(?:自治区)|(?:市)))(.+?(?:(?:地区)|(?:自治州)|(?:市)|(?:盟)))

名前付きキャプチャグループの場合：
(?<Province>.+?(?:(?:省)|(?:自治区)|(?:市)))(?<City>.+?(?:(?:地区)|(?:自治州)|(?:市)|(?:盟)))

上記の場合、これにより次のようになります。
$+{Province} = 云南省<br> $+{City} = 丽江市

これはすべてうまくいっていて、私をかなり遠ざけます。ただし、問題は、他の識別子のサブストリングである可能性のある識別子を考慮しようとする場合です。たとえば、一般的なストリートレベルのエンティティは、村民委員会を意味する「村民委員会」です。分離したいアドレスのセットでは、すべてのアドレスにこれが完全に書き出されているわけではありません。実は、私は「村団」と単なる「村」も見つけました。

問題？これらの要素の純粋な論理和がある場合、次のようになります。

(?<Street>.+?(?:(?:村委会)|(?:村委)|(?:村)))

しかし、何が起こるかというと、保定村委員会（Baoding Village組織委員会）のエンティティがある場合、この怠惰な正規表現は村に立ち寄り、それを1日と呼び、村は潜在的な分離要素の1つであるため、貧しい集会を孤立させます。 。

次のような英語の同等物を想像してみてください。
(?<Animal>.+?(?:(?:Cat)|(?:Elephant)|(?:CatElephant)|(?:City)))

2つの入力文字列があります
。1。「Crapcatelephant」と「crapcity」が必要な「crapcatelephantcrapcity」2。「crapcat」「elephantcity」が必要な「crapcatelephantcity」

ああ、あなたが言う解決策は、事前識別子のキャプチャを貪欲にすることです。だが！同じレベルではない同じ識別子を持つエンティティがあります。

市を例にとってみましょう。それは単に「都市」を意味します。しかし、中国には、郡レベル、州レベル、および市町村レベルの都市があります。この文字が文字列内で2回発生した場合、特に2つの隣接するエンティティで発生した場合、欲張り検索では、欲張り一致が最初のエンティティとして誤ってタグ付けされます。次のように：

广东-省 ; 江门-市 ; 开平-市 ; 三埠-区 石海管-区<br> Guangdong-province ; Jiangmen-City ; Kaiping-City ; Sanbu-District ; Shihaiguan-District

（上記のように、これは手動でセグメント化されていることに注意してください。生データには、連結された文字の文字列が含まれるだけです）

欲張り検索の一致は次のようになります
江门市开平市

これは間違っています。2つの隣接するエンティティを構成要素に分離する必要があるためです。かつては地方都市のレベルにあり、1つは郡レベルの都市です。

元のポイントに戻り、ここまで読んでいただきありがとうございます。分離エンティティに重みを付ける方法はありますか？正規表現で最も高い「重み付けされた」識別子を最初に見つけたいと思います。単純な村の代わりに村民委員会。たとえば、「猫」の代わりに「catelephant」。予備実験では、正規表現パーサーは、分離一致を見つける際に左から右に進んでいるようです。これは有効な仮定ですか？最も頻繁に発生する識別子を選言リストの最初に配置する必要がありますか？

中国語関連の詳細を持っている人を失った場合は、お詫び申し上げます。必要に応じてさらに明確にすることができます。例は実際には中国語である必要はありません。より一般的には、正規表現の選言的一致の仕組みに関する質問だと思います。どのような順序で選言的エンティティを優先し、いつ「呼び出す」かをどのように決定しますか。怠惰な検索のコンテキストで1日」？

ある意味で、怠惰な検索と貪欲な検索の間には、ある種の中間点がありますか？最長/最高加重の分離エンティティの前に見つけることができる最小のビットを見つけますか？怠惰になりますが、徹底するためにできれば、少し余分な努力をしますか？（ちなみに、大学での私の仕事の哲学は？）

貪欲なアルゴリズムの用途は何ですか? 実例？

昨日スーパーマーケットの売り場に立って以来、私の後ろのせっかちで神経質な列を無視しようとしながら、コインの最適な配分をヒューリスティックに見つけようとして、根本的なアルゴリズムの問​​題について考えていました。

_{値が v 1} ,...,v _nのコイン システムが与えられ、限られたコインのストック a ₁ ,...,a _nと、支払う必要のある合計 s が与えられます。_{パーティション x 1} ,...,x _n (with 0<=x _i <=a _i ) を x ₁ *v ₁ +x ₂ *v ₂ +...+xで計算するアルゴリズムを探しています。_n *v _n >= s x ₁ +...+x _n - R(r) の合計が最大になるようにします。ここで、r は変化です。つまり、r = x ₁ *v ₁ +x ₂ *v ₂ + です。 ..+x_n *v _n - s であり、R(r) はレジ係から返されたコインの数です。レジ係はすべてのコインの量に制限がなく、常に最小数のコインを返すと仮定します (たとえば、SCHOENING et al. で説明されている欲張りアルゴリズムを使用して)。また、お金の変更がないことを確認する必要もあります。そのため、最善の解決策は、単純にすべてのお金を提供することではありません (その場合、解決策は常に最適であるため)。

クリエイティブなご意見ありがとうございます。